Deep Dive Into Data Structures and Algorithms: Big O Notation

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.