CODEWITHSUNDEEP
algorithmbig-o
Bombiz
Bombiz

Reputation: 1

Is it always possible to find a constant K to prove big O or big Omega?

So I have to figure out if n^(1/2) is Big Omega of log(n)^3. I am pretty sure that it is not, since n^(1/2) is not even in the bounds of log(n)^3; but I do not know how to prove it without limits. I know the definition without limits is

g(n) is big Omega of f(n) iff there is a constant c > 0 and an integer constant n0 => 1 such that f(n) => cg(n) for n => n0

But can I really always find a constant c that will satisfy this?

for instance for log(n)^3=>c*n^(1/2) if c = 0.1 and n = 10 then we get 1=>0.316.

Upvotes: 0

Views: 73

Answers (1)

Leandro Caniglia
Leandro Caniglia

Reputation: 14858

When comparing sqrt(n) with ln(n)^3 what happens is that

ln(n)^3 <= sqrt(n)                         ; for all n >= N0

How do I know? Because I printed out sufficient samples of both expressions as to convince myself which dominated the other.

To see this more formally, let's first assume that we have already found N0 (we will do that later) and let's prove by induction that if the inequality holds for n >= N0, it will also hold for n+1.

Note that I'm using ln in base e for the sake of simplicity.

Equivalently, we have to show that

ln(n + 1) <= (n + 1)^(1/6)

Now

ln(n + 1) = ln(n + 1) - ln(n) + ln(n)
          = ln(1 + 1/n) + ln(n)
         <= ln(1 + 1/n) + n^(1/6)          ; inductive hypethesis

From the definition of e we know

        e = limit (1 + 1/n)^n

taking logarithms

        1 = limit n*ln(1 + 1/n)

Therefore, there exits N0 such that

        n*ln(1 + 1/n) <= 2                 ; for all n >= N0

so

        ln(1 + 1/n) <= 2/n
                    <= 1

Using this above, we get

        ln(n + 1) <= 1 + n^(1/6)
                  <= (n+1)^(1/6)

as we wanted.

We are now left with the task of finding some N0 such that

ln(N0) <= N0^(1/6)

let's take N0 = e^(6k) for some value of k that we will are about to find. We get

ln(N0) = 6k
N0^(1/6) = e^k

so, we only need to pick k such that 6k < e^k, which is possible because the right hand side grows much faster than the left.

Upvotes: 1

Related Questions