Home|Cheat|Cram|Answers|Chat

DAA Cram Sheet - last hour

Do this for every analysis answer

1. State input size n.
2. Name the basic operation.
3. Set up the sum or recurrence.
4. Solve and give the Theta bound.

Formulas

• S(P)=c+Sp. T(n)=cop x C(n).
• 1+2+..+n = n(n+1)/2. 1+2+..+(n-1)=n(n-1)/2.
• Cavg(seq search)=p(n+1)/2+(1-p)n.
• Master: T(n)=aT(n/b)+f(n); n^(log_b a).

Complexity table

• Sequential O(n); binary O(log n).
• Bubble O(n^2) (best n); selection O(n^2) always; insertion O(n^2) (best n).
• Merge O(n log n); quick O(n log n)/worst O(n^2); heap O(n log n).
• Counting O(n+k); radix O(d(n+k)).

Recurrence table

• T(n)=T(n-1)+1 -> n.
• T(n)=2T(n-1)+1 -> 2^n-1 (Hanoi).
• T(n)=T(n/2)+1 -> log n.
• T(n)=2T(n/2)+n -> n log n.
• T(n)=8T(n/2)+n^3 -> n^3.
• T(n)=2T(n/2)+n^2 -> n^2.
• T(n)=T(n-1)+n -> n^2.

Key numbers

• Largest element: n-1.
• Max-min general 2n-2; D&C 3n/2-2.
• Hanoi moves 2^n-1; n=3 -> 7.
• MCM p={4,10,3,12,20,7} -> m[1,5]=1344.

Home|Cheat|Answers|Top|Chat