Deep Dive Into Data Structures and Algorithms: Big O Notation
Tags: python, datastructures, beginners
Published: 2022-07-07 09:02:16

In my [previous article](https://dev.to/crunchyanomaly/introduction-to-data-structures-and-algorithms-34lb) 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.