Some Math Notes

Growth of functions:

Let f(n) and g(n) be functions.

· If lim f(n)/g(n) = oo then g(n) is O(f(n)) i.e. f(n) grows faster

· If lim f(n)/g(n) = 0 then f(n) is O(g(n)) i.e. g(n) grows faster

· If lim f(n)/g(n) = c, where 0 < c < oo, then f(n) and g(n) grow at the same rate.

Formulas:

• Sum(1:n)(i) = n(n+1)/2
• Sum(1:n)(i^k) = O(n^k+1)
• Sum(0:n)(aⁱ) = (aⁿ⁺¹ – 1)/(a-1) for a > 1
• Sum(0:n)(a^-i) < a/(a-1) for a > 1

Running Time of Program Segments

• RT(s1:s2;...sn) = max{RT(s1),RT(s2),...RT(sn)}
• RT( if(s1);else s2;) = max(RT(s1),RT(s2));
• RT( for( int i = 0; i < n; i++ ) s;) = n*RT(s);

Recurrence Relations

All of the following have a base case of T(0) = a.

• T(n) = T(n-1) + b => T(n) = is O(n).
• T(n) = 2T(n-1) + b => T(n) = is O(2ⁿ).
• T(n) = T(n-1) + bn => T(n) = is O(n²).

All of the following have a base case of T(1) = a.

• T(n) = T(n/2) + b => T(n) is O(log(n)).
• T(n) = 2T(n/2) + b => T(n) is O(n).
• T(n) = 2T(n/2) + b*n => T(n) is O(nlog(n)).
• T(n) = T(n/2) + b*n => T(n) is O(n).
• T(n) = cT(n/2) + b => T(n) is O(c^log(n))