- 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