1

Big-Oh Notation Let f and g be functions from positive numbers to positive numbers. f (n) is O(g(n)) if there are positive constants C and k such that: f (n) ≤ C g(n) whenever n > k f (n) is O(g(n)) ≡ ∃C ∃k ∀n (n > k → f (n) ≤ C g(n)) To prove big-Oh, choose values for C and k and prove n > k implies f (n) ≤ C g(n). Standard Method to Prove Big-Oh 1. Choose k = 1. 2. Assuming n > 1, find/derive a C such that f (n) C g(n) ≤ =C g(n) g(n) This shows that n > 1 implies f (n) ≤ C g(n). Keep in mind: • n > 1 implies 1 < n, n < n2, n2 < n3, . . . • “Increase” numerator to “simplify” fraction.

2

Proving Big-Oh: Example 1 Show that f (n) = n2 + 2n + 1 is O(n2). Choose k = 1. Assuming n > 1, then f (n) n2 + 2n + 1 n2 + 2n2 + n2 = < =4 2 2 g(n) n n Choose C = 4. Note that 2n < 2n2 and 1 < n2. Thus, n2 + 2n + 1 is O(n2) because n2 + 2n + 1 ≤ 4n2 whenever n > 1. Proving Big-Oh: Example 2 Show that f (n) = 3n + 7 is O(n). Choose k = 1. Assuming n > 1, then f (n) 3n + 7 3n + 7n 10n = < = = 10 g(n) n n n Choose C = 10. Note that 7 < 7n. Thus, 3n + 7 is O(n) because 3n + 7 ≤ 10n whenever n > 1.

3

Proving Big-Oh: Example 3 Show that f (n) = (n + 1)3 is O(n3). Choose k = 1. Assuming n > 1, then f (n) (n + 1)3 (n + n)3 8n3 = < = 3 =8 3 3 g(n) n n n Choose C = 8. Note that n + 1 < n + n and (n+n)3 = (2n)3 = 8n3. Thus, (n+1)3 is O(n3) because (n + 1)3 ≤ 8n3 whenever n > 1. Proving Big-Oh: Example 4 Show that f (n) = Σ i is O(n2). i=1 n

Choose k = 1. Assuming n > 1, then f (n) Σn i Σn n n2 = i=1 ≤ i=1 = 2 = 1 g(n) n2 n2 n Choose C = 1. Note that i ≤ n because n is the upper limit. Thus, Σn i is O(n2) because i=1 n i ≤ n2 whenever n > 1. Σi=1

4

How to Show Not Big-Oh f (n) is not O(g(n)) ≡ ∀C ∀k ∃n (n > k ∧ f (n) > C g(n)) Need to prove for all values of C and k. C and k cannot be replaced with constants. Choose n based on C and k. Prove that this choice implies n > k ∧ f (n) > C g(n) Standard Method to Prove Not-Big-Oh: 1. Assume n > 1. 2. Show: f (n) h(n) g(n) ≥ = h(n) g(n) g(n) where h(n) is strictly increasing to ∞. 3. n > h−1(C) implies h(n) > C, which implies f (n) > C g(n). So choosing n > 1, n > k, and n > h−1(C) implies n > k ∧ f (n) > C g(n).

5

Proving Not Big-Oh: Example 1 Show that f (n) = n2 − 2n + 1 is not O(n). Assume n > 1, then f (n) n2 − 2n + 1 n2 − 2n = > =n−2 g(n) n n n > C + 2 implies n − 2 > C and f (n) > Cn. So choosing n > 1, n > k, and n > C + 2 implies n > k ∧ f (n) > Cn. • “Decrease” numerator to “simplify” fraction. Proving Not Big-Oh: Example 2 Show that f (n) = (n − 1)3 is not O(n2). Assume n > 1, then: n3 − 3n2 + 3n − 1 n3 − 3n2 − 1 f (n) = > 2 g(n) n n2 n3 − 3n2 − n2 =n−4 > 2 n n > C + 4 implies n − 4 > C and f (n) > Cn2. Choosing n > 1, n > k, and n > C + 4 implies n > k ∧ f (n) > Cn2.

6

Proving Not Big-Oh: Example 3 Show that f (n) = n2/2 is not O(n). Assume n > 1, then: n2/2 n2/2 − 1 n2/2 − n f (n) = > > g(n) n n n = n/2 − 1 n > 2C + 2 → n/2 − 1 > C and f (n) > Cn. Choosing n > 1, n > k, and n > 2C +2 implies n > k ∧ f (n) > C n.