Specification and complexity - algorithm

Specification and complexity - algorithm

1. Algorithm Specification
and Complexity

2. Algorithm Criteria
Every Algorithm must have satisfied following
Criteria:
01/04/16 2

3. Algorithm Specification
01/04/16 3

4. Algorithm Specification (Cont.)
01/04/16 4

5. Algorithm Specification (Cont.)
01/04/16 5

6. Algorithm Specification (Cont.)
01/04/16 6

7. Algorithm Time Complexity
Asymptotic Notations
Q, O, W
01/04/16 7
 Q (Theta) (Average Case)
 O (Big-oh) (Worst Case)(Upper Bound)
 W (Omega) (Best case)(Lower Bound)

8. Algorithm Time Complexity
(Cont.)
01/04/16 8
Example: f(n) = 3n
2
+ 17
W(1), W(n), W(n
2
)  lower bounds
O(n
2
), O(n
3
), ...  upper bounds
Q(n
2
)  exact bound

9. Algorithm Time Complexity
(Cont.)
01/04/16 9
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 */
10n
2
+4n+2=O(n
2
) /* 10n
2
+4n+2£11n
2
for n³5 */
6*2
n
+n
2
=O(2
n
) /* 6*2
n
+n
2
£7*2
n
for n³4 */

10. Algorithm Time Complexity
(Cont.)
01/04/16 10
Relations Between Q, W, O:
Theorem : For any two functions g(n) and f(n),
f(n) = Q(g(n)) if
f(n) = O(g(n)) and f(n) = W(g(n)).
Theorem : For any two functions g(n) and f(n),
f(n) = Q(g(n)) if
f(n) = O(g(n)) and f(n) = W(g(n)).
I.e., Q(g(n)) = O(g(n)) Ç W(g(n))
In practice, asymptotically tight bounds are obtained from asymptotic upper and
lower bounds.

11. Algorithm Space Complexity
S(P)=C+S
P(I)
01/04/16 11
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 (S
P
(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 To Everybody
01/04/16 12