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.