Asymptotic Analysis

  • Evaluate performance of algorithm in term of input size
  • Order of growth in performance in respective of no of elements.
  • Cases to analyze algorithm
    • Worst Case : upper bound O(n)
    • Average Case
    • Best Case: lower bound O(1)

 Notations:

  • Theta Notation Θ: Bound algo from above & below
  • Big O Notation : defines Upper bound
  • Omega Notation Ω: defines lower bound

 Loops:

  • O(1)
    • set of non-recursive and non-loop statements
    • A loop or recursion that runs a constant number of times is also considered as O(1).
  • O(n)
    • If loop is incremented/decremented by constant value
  • O(nc)
    • No of nested loops
  • O(logn)
    • If loop variable is divided/multiplies by constant value
  • O(loglogn)
    • If loop variable reduced or increased exponential by constant amount

Recurrence

  • Ways to solve recurrence
    • Substitution Method: guess solution then prove that is correct
  • Recurrence Tree Method
    • Summation of time taken by all recurrence calls
  • Master Method
    • Direct way to get solution
    • Work on following
      • If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)
      • If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)
      • If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n))

Amortized Analysis

  • Used for algo in which occasional operation is slow but other operation are fast.
  • Sequence of operation analysed and guarantee of worst case time below of that operation
  • Data structures whose operations are analyzed using Amortized Analysis are Hash Tables, Disjoint Sets and Splay Trees.
  • Dynamic table concept

Space Complexity

  • Space taken by algorithm with respect to input size
  • Pseudo-polynomial Algo
    • Algo whose worst case complexity depends on numeric value of input
    • Counting frequency of positive number in array
      • Solution is find maximum element and iterate from 1 to max
      • This algo require time on basis of value of input
    • NP-Complete problem can be solved using this algo are weakly polynomial
  • NP-Complete
    • Status is unknown
  • P : No of problem solved by deterministic machine in polynomial time
  • NP : Set of decisions problems that can be solved by Nondeterministic machine in polynomial time
  • P is subset of NP
  • A decision problem L is NP-Complete if
    • L is in NP (solution can be verified quickly but no efficient solution)
    • Every Problem in NP can be reducible to L
    • If a problem follow property second only not 1 then that is NP-Hard
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: