[Ap0C552]

I am working on proofs for big o. Like proving f(n) is in bog-o g(n).

I am just wondering if there is anyone who is capable at this, would they be gracious enough to just take a peek at my work and let me know if I am doing anything that makes sense.

Here is one I just did.

f(n)=nlogn+n+logn
g(n)=nlogn

Proving that f(n) is in g(n) by showing there is a value M > 0, and a value K > 0 such that for every value of n>K f(n)<=M(g(n)).

Let K= 1 let M=3

1. n>K
2. n>1
3. nlogn>logn
4. nlogn>n
5. nlogn+nlogn+nlogn>nlogn+n+logn (from 3,4)
6. 3(nlogn)>nlogn+n+logn

Does this make sense?

This post has been edited by Ap0C552: 02 October 2011 - 05:15 PM

[elgose]

That makes sense (and is the usual process to solve these problems) except for your choices for k and M. If M=3, then k>=4. You can always use a calculator to check your logic:

f(x) = xlogx+x+logx
g(x) = 3xlogx

f(1) = 1, f(2) = 2.90, f(3) = 4.90, f(4) = 7.01, f(5) = 9.19
g(1) = 0, g(2) = 1.80, g(3) = 4.29, g(4) = 7.22, g(5) = 10.48

Note: If you're using log base-2, which depending on if this is for a CS class rather than a math class may be the case, then k>=2 would be fine.

This post has been edited by elgose: 02 October 2011 - 06:43 PM

[blackcompe]

Let f(n) = nlogn + n + logn
Let g(n) = nlogn

Show that f(n) is Big-Oh g(n), that is f(n) <= Cg(n) for all n > n₀.

So you think that C = 3 and n₀ = 1, makes this statement true for n > n₀. Let n = 2.

f(2) = 2(log2(2)) +2 + log2(2) = 5
Cg(2) = 6(log2(2)) = 6

So, f(2) < Cg(2).

Let n = 10.

f(10) = 10(log2(10)) + 10 + log2(10) = 46.54

Cg(10) = 30(log2(10)) = 99.66

And, f(10) < Cg(10). Let n = 1000000000.

f(1000000000) = 1000000000(log2(1000000000)) +1000000000 + log2(1000000000) = 3.09 × 10¹⁰

Cg(1000000000) = 3000000000(log2(1000000000)) = 8.97 × 10¹⁰

So, yes, C = 3 and n₀ = 1 make that statement true.

[Ap0C552]

Thanks so much!! Really appreciative for that help.

I might be back here soon as I continue to educate myself (the prof and text suck lol!)