Algorithms Summary Points – Part 2: Intro to Analyzing Complexity and Binary Search

This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

Intro to Analyzing Complexity and Binary Search

The running time of a for loop is at most the: 

  • number of iterations * running time for the statements in the loop 

The running time of nested for loops is the: 

  • Running times of outer iterations * running times of inner iterations 

The running time of consecutive for loops is the sum of their running times. 

The running time of an if statement is at most the running time of the condition plus the larger of the running times of the statements in the blocks. 

Binary Search 

  • Only works if the input array is already sorted! 
  • Keeps track of the lower and upper bound of the section of the array to search 
  • Returns false if the lower bound is greater than the upper bound – this is the first base case 
  • Divides the array into 2 
  • Checks if the value is at the mid – this is the second base case 
  • If not and the value is less than the mid, it recursively searches the left side (uses the midpoint to get its upper bound) 
  • If not and the value is greater than the mid, it recursively searches the right side (uses the mid to compute the lower bound) 
  • Worst Case Running Time is O(log n) 
  • This can easily be seen since the input is divided by 2 each time. So, in the worst case, we will have log(n) self-calls till the input is empty. The number of possible terms is any sequence divided this way is 1+log(n). 
  • Best Case is O(1) – if the element is at the mid 

Master Formula

The master formula is used for Divide and Conquer algorithms only, which use recursion. 

When the complexity of a function T(n) is defined in terms of itself, the function uses recursion. 

To compute running time of binary search, we can: 

  1. Calculate the number of primitive operations and then use the master formula to get the complexity. 
  2. Compute the number of self-calls. With the knowledge that the self-calls lead to a sequence where n is divided by two every time (n/2 ..n/4…n/8…), we realize 1+log n terms, which gives us O(log n) 

Leave a Reply

Your email address will not be published. Required fields are marked *