To get a clear picture of this Recitation, kindly read the Recitation handout (PDF).

The first question to ask ourself is **What is Big-O notation?**

Big-O notation gives us a upper bound on how long somethings will execute. The important thing to remember is that this is not time bound. So Big-O does not take how long a program will execute, it tells **how many steps** it will take to execute a program.

Big-O notation cannot predict accurately for small inputs, but for a very large input how the algorithm performs is what we are interested in.

Consider this scenario. We have 2 Algorithms and their Big-Oh representation.

A1 : O(n) A2 : O(n^2) A2/A1 : O(n^2)/O(n) : O(n^2)

So as we can see in the above case, irrespective of which computer you are running these algorithms, `A2`

will always be slower that `A1`

by `n^2`

times.

## Some Common Big-O Notations

- O(1) :
**Constant Time**, What this means is, it does not depends on the size of the input, so O(1) = O(100) = O(2^100). The reason being, it will not change based on the input. - O(log n):
**Logarithmic Time**, Any base log is same Big-O because the variation is minimal. This is the fastest time bound for Search. - O(n) :
**Linear Time**, This means we have to look at each input at least once. - O(n log n) : This is the fastest time bound for Sorting.
- O(n^2) :
**Quadratic Time**, This is the complexity when we consider inner loops. - O (2^n) :
**Exponential Time**, This is really big.

Always remember:-

O(n^k) < O(k^n) Polynomial Time < Exponential Time

### Some Questions

- Does O(100 n^2) = O(n^2)
- Does O(1/4 n^3) = O(n^3)
- Does O(n) + O(n) = O(n)

All the above are *True*, because Big -O is bothered with the higher power.

## Constant Time Examples

Consider the below example:-

def inc(x): return x+1

even this is constant time:-

def bar(x, y): z = x + y w = x * y q = (w**z) % 870 return 9*q

## Linear Time

Here is an example of linear time code:-

def mul2(x, y): result = 0 for i in range(y): result += x return result

The `for`

loop in the above code is an indication that it will be atleast `O(n)`

Not always, the operation inside a `for`

loop is constant time, consider this example:-

def count_same_ltrs(a_str, b_str): count = 0 for char in a_str: if char in b_str: count += 1 return count

The above is not linear, because the `if`

condition also have to traverse the `b_str`

, so this is `O(n^2)`

## Recursion

Consider the below example for recursion in factorial program.

def r_factorial(n): if n <= 0: return 1 else: return n*r_factorial(n-1)

To find the complexity of a recursive function you have to find out the number of recursive call it will make. So for the above example it will make `n`

calls. So this will be Linear.

Now consider this example:-

def foo(n): if n <= 1: return 1 return foo(n/2) + 1

So solve this we need to find this

n/2^n = 1 n = 2^k k = log n

So this is `O(Log N)`

## Factorial

For a factorial, we might consider that it is linear because of this equation:-

fib(n) = fib(n - 1) + fib(n -2)

But it is not, if we draw the call structure, we will see a tree. As shown below:-

So as you can see, the depth of the tree is n, and at each level we have a branching factor of 2, so a loose calculation will give a complexity of `O(n^2)`