[Cs4800] Proving big O claims

[Karl Lieberherr]

Here is the proof I was looking for in the lecture: We need product rules.
The text book only covers summation rules.

Product rules:

If f1 in O(g1) and f2 in O(g2) then f1*f2 in O(g1*g2) [product rule 1]

f*O(g) in O(f*g) [product rule 2]

We want to prove: n^(1/2) in O(n/log(n))

Start with:
log(n) in O(n^(1/2)) (from calculus)

=> [multiply by n^(1/2) using product rule 2]
n^(1/2) * log(n) in O(n)
=> [multiply by 1/log(n) using product rule 2]
n^(1/2) in O(n/log(n))
qed

A nice simple derivation.

-- Karl
-------------- next part --------------
HTML attachment scrubbed and removed