Algorithm Master Theorem

Question

How to check if f(n) is polynomially greater than g(n)?

Answer 1

“Polynomially greater” check of sqrt(n) vs n:

We say f(n) is polynomially greater than g(n) if

 

Now check:

That is indeed a polynomial factor (with ε=0.5).

---

“Polynomially greater” check of 1 vs logn:

For polynomially greater, we need:

But:

• For any ε>0, nε eventually grows much faster than logn.

• So no such ε exists.

• So: logn grows faster than 1, but NOT by a polynomial factor.