DAA Answers 3 - Asymptotic notation

DAA-Q20 O, Omega, Theta

O (upper): t(n)<=c.g(n) for all n>=n0 (positive c).
Omega (lower): t(n)>=c.g(n) for all n>=n0.
Theta (tight): c1.g(n)<=t(n)<=c2.g(n) for all n>=n0. Theta is the most precise.

DAA-Q21 Little-oh

f(n)=o(g(n)): for every c>0 there is n0 with f(n)<c.g(n) for all n>=n0 (growth strictly slower). E.g. n=o(n^2), but n^2 is not o(n^2).

DAA-Q22 Order of growth

Performance as a function of input size n; keep the leading term, drop constants. 2^n and n! are exponential growth functions.

DAA-Q23 Prove (a) 3n+2=O(n), (b) 8n^2+2n-3=Omega(n^2), (c) 3n+2=Theta(n)

(a) 3n+2<=4n, n>=2. (b) 8n^2+2n-3>=7n^2, n>=1. (c) 3n<=3n+2<=4n, n>=2.

DAA-Q24 Efficiency classes

1 constant; log n binary search; n linear; n log n merge/quick/heap; n^2 simple sorts; n^3 matrix mult; 2^n Hanoi; n! combinatorial. Order: 1<log n<n<n log n<n^2<n^3<2^n<n!

DAA-Q25 Useful property

O(g1)+O(g2)=O(max{g1,g2}); also for Omega and Theta. Total governed by the slower part, e.g. O(n)+O(n^2)=O(n^2).

DAA-Q26 Control structures

Sequencing: sum then max. If-then-else: condition + max rule. For loop: nested loops multiply (O(n^2)). While loop: track the decreasing function / treat as recursive.