Into to Algorithms

So one of the most basic algorithms we can study to get used to time complexity is the linear search algorithm. We will also the most basic data structure, Here is an array in Ruby.

a = [1,2,3,4,5,6,7,8,9]

So let’s say we want to find the element 9 in the array. How do we find this in the array? As a human all you need to do is look and viola, there it is! But a computer is not as smart as you are. It can only look at one element of the array at a time.

The simplest way to search for an element is to do a linear search, loop through the array until you find the element:

def find(a, elem)
  i = 0
  for i in 0...a.length
    if a[i] == elem
      return i
    else
      return -1
    end
end

Here we return the index if we find the element. And if not, then we return -1 and we can check in our calling code that we didn’t find the element because the index is -1

In the worst case scenario, the element will be at the end of the array. If the length of the array is N then we will have to iterate through the loop N times until we reach the last element and we return the index or -1 if we didn’t find the element. So everytime we search for an item we need to either search N times or if the element is in middle of the array we need to search (1/2)N or (1/10)N etc…

Basically we can represent the amount of operation, or time complexity — the amount of steps we need to complete the algorithm as C*N. C is a constant that changes based on the exact input to our algorithm. The common way to represent time complexity is to say O(N) or “on the order of N”.

Now, is the linear search the fastest way to search through an array? Actually it is not! If our element is half-way through the array or one-fourth of the way through the array then as our array gets larger and larger the amount of operations we perform goes linearly, we are not efficiently limiting our search space based on the structure of our data. When we can make no assumptions about our array, in other words, if the elements are most likely jumbled the only thing we can search for an item is using linear search. That’s the best we can do! BUT if we know our array is sorted, we can search much faster using recursion. If our elements are sorted, we can divide our array into smaller arrays we can search through, thus limiting where we search and the amount of elements we consider. Lets look at dividing the array in half, we split the array in half and look at the element in the middle as our “fork” in the road. If our element in consideration is greater, look at the right half of the array, if it’s less than, look in the left half. Here’s the code:

def bin_search(a, elem, p, r)
  if p < r
    q = a[(p + r)/2]
  if a[q] == elem
    return q
  elsif elem < a[q]
    bin_search(a, elem, p, q - 1)
  else
    bin_search(a, elem, q + 1, r)
  end
  elsif a[p] == elem
    return p
  else
    return -1
  end
end

Here we split the array in half recursively, we define a beginning index p and an ending index r and compute the middle using the familiar formula

q = (p + r)/2

We then check if a[q] is our element or if we have a length 1 array with p == r then we check if a[p] is the element. Otherwise we return -1 to indicate the element is not in our array.

Now to analyze the time complexity of this Algo, we are going to learn about trees!

So we start out with the full array and then consider searching 2 distinct sub arrays, either the right half or left half where a[q] is the fork in the road thats splits the two paths. The same happens with either path, it gets forked into another 2 paths, and so on…

Animated comparison of Binary vs Sequential search — https://www.interviewbit.com/courses/programming/topics/binary-search/

https://s3-us-west-2.amazonaws.com/ib-assessment-tests/problem_images/binary_search.gif

The above is an example of merge sort. At each division of the problem merge sort perform an N-time merging operation. We can use the same structure to look at what happens with binary search. Instead of performing an O(n) step at each level we just perform a constant step (computing q from p and r) and since we have LogN levels, the overall complexity is just O(LogN) compared to O(NlogN) for merge sort.