Specification and complexity - algorithm

Specification and complexity - algorithm

• 1.
  Algorithm Specification and Complexity
• 2.
  Algorithm Criteria Every Algorithmmust have satisfied following Criteria: 01/04/16 2
• 3.
  Algorithm Specification 01/04/16 3
• 4.
  Algorithm Specification (Cont.) 01/04/164
• 5.
  Algorithm Specification (Cont.) 01/04/165
• 6.
  Algorithm Specification (Cont.) 01/04/166
• 7.
  Algorithm Time Complexity AsymptoticNotations Θ, O, Ω 01/04/16 7  Θ (Theta) (Average Case)  Ο (Big-oh) (Worst Case)(Upper Bound)  Ω (Omega) (Best case)(Lower Bound)
• 8.
  Algorithm Time Complexity (Cont.) 01/04/168 Example: f(n) = 3n2 + 17  Ω(1), Ω(n), Ω(n2 )  lower bounds  O(n2 ), O(n3 ), ...  upper bounds  Θ(n2 )  exact bound
• 9.
  Algorithm Time Complexity (Cont.) 01/04/169 Examples (For Practices): 3n+2=O(n) /* 3n+2≤4n for n≥2 */ 3n+3=O(n) /* 3n+3≤4n for n≥3 */ 100n+6=O(n) /* 100n+6≤101n for n≥10 */ 10n2 +4n+2=O(n2 ) /* 10n2 +4n+2≤11n2 for n≥5 */ 6*2n +n2 =O(2n ) /* 6*2n +n2 ≤7*2n for n≥4 */
• 10.
  Algorithm Time Complexity (Cont.) 01/04/1610 Relations Between Θ, Ω, O: Theorem : For any two functions g(n) and f(n), f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)). Theorem : For any two functions g(n) and f(n), f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)). I.e., Θ(g(n)) = O(g(n)) ∩ Ω(g(n)) In practice, asymptotically tight bounds are obtained from asymptotic upper and lower bounds.
• 11.
  Algorithm Space Complexity S(P)=C+SP(I) 01/04/1611  Fixed Space Requirements (C) Independent of the characteristics of the inputs and outputs  instruction space  space for simple variables, fixed-size structured variable, constants  Variable Space Requirements (SP(I)) depend on the instance characteristic I  number, size, values of inputs and outputs associated with I  recursive stack space, formal parameters, local variables, return address
• 12.
  Any Questions????? Thanks ToEverybody 01/04/16 12