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.
*T**he 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:

- Calculate the number of primitive operations and then use the master formula to get the complexity.
- 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)