Runtime concepts

Recurrence tree of T(n) = aT(n/b) + f(n),

• Work done at root is f(n)

• Work done at all leaves is    where c is

• Height of recurrence tree is 

Also note:

 

• O(1): If it doesn’t contain loop, recursion and call to any other non-constant time function

• O(n): If the loop variables is incremented / decremented by a constant amount

• O(n^c): Time complexity of nested loops is equal to the number of times the innermost statement is executed

• O(Logn): If the loop variables is divided / multiplied by a constant amount.

• O(LogLogn): If the loop variables is reduced / increased exponentially by a constant amount.

Master theorem

The master theorem concerns recurrence relations of the form:

• n is the size of the problem.

• a is the number of subproblems in the recursion.

• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)

• f (n) is the cost of the work done outside the recursive calls.

Case 1

If   

Where  

Then 

Case 2

If   k ≥ 0 and 

Where 

Then 

Case 3

If     where 

and    for some constant and sufficiently large n

Then