Deep Dive Into Data Structures and Algorithms: Big O Notation

Millicent Kinoti — Thu, 07 Jul 2022 09:02:16 +0000

In my previous article I gave a brief introduction on data structures and the different types. In this article, we will dive expound on ways of analyzing the efficiency of algorithms.

Binary Search

Binary search is an algorithm whose input is a sorted list of elements. Suppose you are searching for a word in a dictionary starting with M. You could start at the beginning and keep flipping until you get to M; but this would be a bad approach. It makes more sense starting from near the middle.
In binary search, if the element you are looking for is in the list, it returns its position, otherwise None. Binary search only works when your list is sorted.

Let's implement binary search in python

The binary_search function takes a sorted array nums and an item.

def binary_search(nums, item):

If the item is in the array, the function returns it position. To keep track of what part of array you have to search through, use low for the lower part of the array and high for the upper part of the array.

low = 0
high = len(nums) - 1

While you haven't narrowed it down to one element check the mid element.

while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]

If the guess is equal to the item, the index is returned. If the guess is too low, you update low accordingly and if too high, update high.

 if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

Full Code:

def binary_search(nums, item):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = nums[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None

nums = [20, 38, 74, 90, 98, 110]
print(binary_search(nums, 98))
print(binary_search(nums, 22))

Now let's run the code

$ python3 binary_search.py   
4
None

The first statement returns 4, since 98 is at index 4 on the list and the second statement returns None since 22 is not on the list.

Running time
The running time of an algorithm grows with the input size, although it may vary for different inputs of the same size. Binary search runs in logarithmic time. If a list has 128 names, the maximum number of steps it would take is 7(2 pow 7 is 128).

Big O Notation

Big O notation is a special notation that is used to show how an algorithm scales with respect to the size of its growth.Growth can be sublinear, linear, superlinear etc. You need to know how the running time increases as the size of the list increases. It establishes a worst case scenario. Big O notation lets you compare the number of operations. For example, binary search needs log n operations to
to check a list of size n. The running time in Big O notation is O(log n).

Common Big O run times sorted from fastest to slowest:

O(log n) -known as log time. Example : Binary search
O(n) - known as linear time. Example : Simple search
O(n * log n) : A fast sorting algorithm like quicksort
O(n2) : A slow sorting algorithm like selection sort.
O(n!) : A really slow algorithm like the travelling salesperson.

Conclusion
The speed of an algorithm is not measured in seconds but in growth of the number of operations. Instead, we talk about how quickly the tun time of an algorithm increases as the size of the input increases. In my next article, we will cover on the different Big O run times.

Introduction to Data Structures and Algorithms

Millicent Kinoti — Tue, 21 Jun 2022 10:05:58 +0000

Data Structure

A data structure can be defined as a specialized method of organizing and storing data so that execution of operations on data can be more efficient. Data can be organized in many ways such as lists or dictionaries in Python.

Data structures can be of two types: primitive and non primitive

Primitive data structures
Primitive data structures can simply be defined as data types. Data types are elementary. They cannot be further subdivided. They include int, char, double.

Non Primitive data structures
Non primitive data structure is a data structure which can be used to store data of more than one type.
Non primitive data structure can be subdivided into two categories:

Linear data structure.
Non-linear data structure

1. Linear data structure
The elements of a linear data structure are stored in a sequential manner. Types of linear data structure include array, list, stack and queues.

Array
An array is a data structure that stores elements of the same data type in contiguous and adjacent memory locations. An item stored in an array is called an element and an index indicates the position of the element within in an array. The index of an array starts from 0, therefore if an array has 10 elements, the index will start from 0 to 9.

List
A list is a data structure which stores elements in an ordered manner. It allows repetition and therefore a single piece of data can occur more than once in a list.

Stack
A stack is data structure that holds an ordered, linear sequence of items. It uses the Last In, First Out(LIFO) structure to access the elements in the stack. A real life example is that of a stack of plates. You can only access the plates from the top of the stack and can only add a plate to the top of the stack.

Queue
A queue is similar to a stack but it is open at both its ends. It uses the First In, First Out technique to access the elements. Data insertion occurs at the rear end or the tail of the queue whole deletion at the front end or the head of the queue.

2. Non Linear Data Structure
The elements are not arranged sequentially rather in a hierarchical manner. Elements cannot be traversed in a single run. Examples include trees and graphs

Trees
A tree is a hierarchical data structure that consists of nodes connected by edges. A node is a structure which contains data and pointers to its child nodes.An edge is used to connect two nodes. Every node except the root node is connected by exactly one incoming edge from another node.

Graphs
A graph is a data structure made up of nodes or vertices and edges

Algorithms

An algorithm is a set of well-defined instructions to solve a particular problem. For example, an algorithm to add two numbers can be as follows:

Step 1: Start.
Step 2: Declare variables num1, num2 and sum.
Step 3: Read values num1 and num2.
Step 4: Add num1 and num2.
Step 5: Assign the result to sum. sum ← num1 + num2.
Step 6: Display sum.
Step 7: Stop

Characteristics of an algorithm

Finiteness - Must terminate after a finite number of steps.
Unambiguous - Should be clear and unambiguous.
Independent - Should be independent of any programming code
Input - It should have 0 or more well defined inputs.
Output - It should have 1 or more well-defined outputs.
Effectiveness - It must be possible to perform each step of the algorithm correctly and in a finite amount of time. Effectiveness is determined by:

Space complexity :The memory space needed by a specific algorithm to be executed.
Time complexity: The time required by a program to be completed.