"No one is harder on a talented person than the person themselves" - Linda Wilkinson ; "Trust your guts and don't follow the herd" ; "Validate direction not destination" ;

December 19, 2009

Algorithms - Time Complexity

Time Complexity of For Loops
1. Sum = 0;
    for(i=0; i>n; i++)
  Complexity is O(N)  - Since the loop is executed only once

2. Sum = 0;
    for(i=0; i<n; i++)
         for(j=0; j<n; j++)
 Complexity is O(N Square) - Two For loops

3. Sum = 0;
    for(i=0; i<n; i++)
        for(j=0; j<n*n; j++)
 Complexity is O(N3) - N Power3

'O' Notation
  • O(g(n)) is a set of functions, f, such that
  • f(n) < cg(n) - g is an upper bound of f
  • f is O(g) is transitive. If f is O(g) and g is O(h) then f is O(h)
  • Exponential functions grow faster
  • Lograthmic functions grow slower
Omega notation
  • set of functions such that f(n) > cg(n) - g is lower bound of f
Theta notation
theta(g) = O(g) and Omega (g). g is both lower and upper bound of f

Good Tutorial Link

Class P - Set of Problems which will have solutions with polynomial time complexity. E.g - Euler's Problem

Class NP - (Non Deterministic Polynomial) - Problem which can be solved by a series of guessing (non-deterministic) steps but whose solution can be verified as correct in polynomial time is said to lie in class NP. E.g Hamilitonian Problem

Sort Algorithms Time Complexity
  • Insertion Sort - O(N Square)
  • Bubble Sort - O(N Square)
  • Heap Sort - O(NlogN)
  • Quick Sort - O(NlogN)
  • Radix Sort - O(N)

No comments: