mathlittle-o

Prove little-O from first principles


Prove that f(n) = 2010n^2 + 1388n belongs to o(n^3)

Little-O Definition

My work so far: This must be true: for ALL constats c>0, there exists a constant n0>0 such that 0<=2010n^2 + 1388n<=cn^3 for all n>n0

By simplifying we get: c>= 2010/n + 1388/n^2

Not sure what to do next to find n0.


Solution

  • You might have an easier time with an equivalent definition of little-o notation: we say that f = o(g) if

    limn → ∞ f(n) / g(n) = 0

    In your case, this means that you'd prove that

    limn → ∞ (2010n2 + 1388n) / n3 = 0

    To see this, note that

    limn → ∞ (2010n2 + 1388n) / n3

    = limn → ∞ (2010n2 / n3) + (1388n) / n3

    = limn → ∞ (2010 / n) + (1388 / n2)

    = limn → ∞ (2010 / n) + limn → ∞ (1388 / n2)

    = 0 + 0

    = 0

    Hope this helps!