6_12_13Asymptotic analysiskfnhlkjsbfbkjs.pdf

sfbsb

1. CS1011E:Program Design
Asymptotic Analysis

2. Algorithm
•An algorithm is a finite sequence of logically related
instructions to solve a computational problem.
Examples:
—Given an integer x, test whether x is prime or not.
—Given a program P, check whether P runs into an infinite loop.
•Properties -Input, Output, Finiteness, Definiteness, Effectiveness

3. Factorial in (Recursive/Iterative)
Example Iterative Algorithm for Factorial
Fact_Iter(n)
for i= 1 to n
fact = fact * i
return fact
Example Recursive Algorithm for Factorial
Fact_Recr(n)
if n = 1
return 1;
else
return (n * fact(n-1))

4. ALGORITHMANALYSIS
Correctness
Foranyalgorithm,aproofofcorrectnessisimportantwhichwill
exhibitthefactthatthealgorithmindeedoutputthedesired
answer.
Amount of work done (time complexity)
The time complexity does not refer to the actual running time of an
algorithm, instead it is the step count: the number of times each
statement in an algorithm is executed.
•The step count focuses on primitive operations along with basic
operations.

5. Space Complexity
•The number of primitive operations increases with the problem size.
•Space complexity is a related complexity measure that refers to the amount
of space used by an algorithm.
•Among the many algorithms for a given combinatorial problem, a natural
question is to find the best algorithm (efficient).

6. IINPUTSIZEANDPRIMITIVEOPERATIONS
INPUT SIZE AND PRIMITIVE OPERATIONSNPUTSIZE
ANDPRIMITIVEOPERATIONS
INPUINPUTSIZEANDPRIMITIVEOPERATIONS
TSINPUTSIZEANDPRIMITIVEOPERATIONS
IZEINPUTSIZEANDPRIMITIVEOPERATIONS
ANDPRIMITIVEOPERATIONS

7. ANALYSISOFALGORITHMSUSINGSTEPCOUNTMETHOD
1Each basic statement like assignment and return have a count of 1.
2If a basic statement is iterated, then multiply by the number of times
the loop is run.
3The loop statement is iterated n times, it has a count of (n + 1). Here
the loop runs n times for the true case and an additional check is
performed for the loop to exit (the false condition).

8. EXAMPLESExamples
1)Sum of elements in an array

9. Example
2) algorithm Fibonacci(n)
algorithm Fibonacci(n) Step Count
if n≤1 1
output ‘n’
else
f2=0 1
f1=1 1
for i=2 to n n
f=f1+f2 n-1
f2=f1 n-1
f1=f n-1
output f 1
Total number of steps 4n+1

10. Order of Growth or Rate of Growth
•Order of Growth or Rate of Growth -A simple characterization
of the algorithms efficiency by identifying relatively significant
term in the step count.

11. Example
•The low order terms in a function are relatively insignificant for largen
n
4
+ 100n
2
+ 10n+ 50~ n
4
i.e., we say thatn
4
+ 100n
2
+ 10n+ 50and n
4
have the same rate of
growth

12. Asymptotic analysis
•Asymptotic analysis is a technique that focuses analysis on the
“significant term”.
•For example, an algorithm with a step count 2n
2
+ 3n + 1, the
order of growth depends on 2n
2
for large n.

13. Asymptotic analysis (cont…)
•To compare two algorithms with running times f(n)and
g(n),we need a rough measurethat characterizes how fast
each function grows.
•Hint:use rate of growth
•Compare functions in the limit, that is, asymptotically!
(i.e., for large values of n)

14. Asymptotic Notations
1.Big-oh Notation (O) -To express an upper bound on the time
complexity as a function of the input size.
2.Omega (Ω) -To express a lower bound on the time
complexity as a function of the input size.
3.Theta (Θ) -To express the tight bound on the time
complexity as a function of the input size.

15. Asymptotic Notations (cont..)
•O notation: asymptotic “less than”:
f(n)=O(g(n)) implies: f(n) “≤” g(n)
•Ω notation: asymptotic “greater than”:
f(n)= Ω (g(n)) implies: f(n) “≥” g(n)
•Θ notation: asymptotic “equality”:
f(n)= Θ (g(n)) implies: f(n) “=” g(n)

16. Asymptotic notation-Big O notation

17. Examples

18. •We say f
A(n)=30n+8is order n, or O (n)
It is, at most, roughly proportionalto n.
•f
B(n)=n
2
+1 is order n
2
, or O(n
2
). It is, at most, roughly proportional to
n
2
.
•In general, any O(n
2
) function is faster-growing than any O(n)
function.

19. 19
Visualizing Orders of Growth
•On a graph, as
you go to the
right, a faster
growing
function
eventually
becomes
larger...
f
A(n)=30n+8
Increasing n
→
f
B(n)=n
2
+1
Value of function
→

20. 20
More Examples …
•n
4
+ 100n
2
+ 10n+ 50 is O(n
4
)
•10n
3
+ 2n
2
is O(n
3
)
•n
3
-n
2
is O(n
3
)
•constants
–10 is O(1)
–1273 is O(1)

21. 21
Examples
–2n
2
= O(n
3
):
–n
2
= O(n
2
):
–1000n
2
+1000n = O(n
2
):
–n = O(n
2
):
2n
2
≤ cn
3
⇒2 ≤ cn ⇒c = 1 and n
0= 2
n
2
≤ cn
2
⇒c ≥ 1 ⇒c = 1 and n
0= 1
1000n
2
+1000n ≤ 1000n
2
+ n
2
=1001n
2
⇒c=1001 and n
0= 1000
n ≤ cn
2
⇒cn ≥ 1 ⇒c = 1 and n
0= 1

22. 22
No Uniqueness
•There is no unique set of values for n
0and c in proving the asymptotic bounds
•Prove that 100n + 5 = O(n
2
)
–100n + 5 ≤ 100n + n = 101n ≤ 101n
2
for all n ≥ 5
n
0= 5 and c = 101is a solution
–100n + 5 ≤ 100n + 5n = 105n ≤ 105n
2
for all n ≥ 1
n
0= 1 and c = 105is also a solution
Must findSOMEconstants c and n
0that satisfy the asymptotic notation relation

23. 23
Asymptotic notations-Big Omega Notation
•Ω-notation
Ω(g(n))is the set of functions
with larger or same order of
growth as g(n)

24. Asymptotic Lower Bound-Big Omega Notation
24

25. Examples
25

26. Remarks
3n
2
+ 2 ≠Ω(n
3
).
Reason:
There does not exist a positive constant c such that 3n
2
+ 2 ≥c.n
3
for
every n ≥n
0 as we cannot bound n by a constant. That is, on the
contrary if 3n
2
+ 2 ≥c.n
3
, then n≤(1/c )is a contradiction. That is on
the contrary if 3n
2
+ 2 ≥c.n
3
, then 3.2
n
≠Ω(n!), and5 ≠Ω(n).

27. 27
Asymptotic notations-Theta notation
•Θ-notation
Θ(g(n))is the set of functions
with the same order of growth
as g(n)

28. 28

29. Examples
1 3n + 10
10
3n ≤3n + 10
10
≤4n, ∀n ≥10
10
⇒3n + 10
10
= Θ(n)
Note that the first inequality captures 3n + 10
10
= Ω(n) and the
later one captures 3n + 10
10
= O(n).
2 10n
2
+ 4n + 2 = Θ(n
2
)
10n
2
≤10n
2
+ 4n + 2 ≤20n
2
, ∀n ≥1, c
1 = 10, c
2 = 20
3 6(2
n
) + n
2
= Θ(2
n
)
6(2
n
) ≤6(2
n
) + n
2
≤12(2
n
), ∀n ≥1, c
1 = 6, c
2 = 12
4 2n
2
+ n lg n + 1 = Θ(n
2
)
2n
2
≤2n
2
+ n lg n + 1 ≤5.n
2
, ∀n ≥2, c
1 = 2, c
2 = 5

30. Remarks
3n + 2 ≠Θ(1).
Reason: 3n + 2 ≠O(1)
3n + 3 ≠Θ(n
2
).
Reason: 3n + 3 ≠Ω(n
2
)
n
2
≠Θ(2
n
).
Reason: n
2
≠Ω(2
n
)

31. Solving Recurrences
1)Substitution Method
2)Recursion Tree Method
3)Master Method

32. Solution for Recurrence relation (cont..)
▪Substitution method
substitute the T(i) repeatedly until ireaches 0 or 1.
▪Recursion Tree
nodes represent cost. Sum up the cost at different levels
▪Master Method
memorize the three cases in upcoming slides

33. Running Time in Recurrence equation

34. Divide and Conquer –Recurrences

35. Recurrence Example 1 by Substitution
•T(n) = 2 T(n/2) + cn
= 2 (2 T(n/4)+ cn/2) + cn
= 4 T(n/4) +2cn
= 4 (2 T(n/8) + cn/4) + 2cn
=8(T(n/8)+3cn
=2^3 (T(n/2^3))+3cn
After k substitutions
T(n)= 2
k
T(n/2
k
)+kcn

36. Recurrence Eq. Example 1 (cont…)
Assume n=2
k
Taking log on both sides
log n=k
T(n)= nT(n/n)+cnlgn
T(n)= nT(1)+cnlgn
=Θ(nlgn)

37. Recurrence Example 2 by substitution
•T(n) = T(n/2) + c
= T(n/4)+ c+c=T(n/4)+2c=T(n/2
2
)+2c
=T(n/8)+3c=T(n/2
3
)+3c
After k substitutions
T(n)= T(n/2
k
)+kc

38. Recurrence Eq. Example 2 (cont..)
Assume n=2
k
Taking log on both sides
log n=k
T(n) = T(n/n)+clgn
T(n) = T(1)+clgn
=Θ??????�??????

39. Recursion Tree Method

40. Cont…
•T(n/2)=2T(n/4) + cn/2=T(n/2)+T(n/2)+ cn/2

41. Cont…

42. Recursion Tree when n=8=2^3

43. Cont…

45. Cont…

46. Master Method
•
Ө
Ω

48. Example 1

49. Example 2

50. Example 3
??????
log
????????????
=O(n
0.793
)
f(n)=??????(??????
log
????????????+??????
) for ε≈0.2
af(n/b)=3(n/4)lg(n/4)≤(3/4)nlgn
=cf(n) for c=3/4
Solution ????????????=Θ�??????=Θ(????????????�??????)
T(n)=3T(n/4)+nlgn
a=3,b=4, f(n)=nlgn

51. Reference
Thomas H Cormen, C E Leiserson, R L Rivest, C Stein (CLRS) “Introduction to
Algorithms”, 3
rd
ed., PHI, 2010