Algorithms - Time Complexity

Time Complexity of For Loops
=========================
1. Sum = 0;
    for(i=0; i>n; i++)
        Sum++;
  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++)
               Sum++;
 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)