Proving/Disproving BigO, and BigTheta

Question

I am having issues fully understanding how to prove some of the following statements.

For instance I have a statement: n^2logn = O(n^2). Correct me if I am wrong, but this states that n^2 is bigO of n^2logn. Meaning that n^2 grows faster than n^2logn. Now how would we go about proving this? I assume that I would need to use proof by induction which I have tried to use but got stuck in the process. Could I re-write this statement as n^2logn <= n^2?

Is it possible to disprove something using induction? For example, disproving n!=O(n^n). Or is it valid to disprove the statement by simply showing that an arbitrary value )let's say greater than 2) does not satisfy the statement?

And finally for clarity, bigTheta states that the equations are equivalent when growing correct?

score 6 · Accepted Answer · edited May 23 '17 at 12:31

6

The claim n^2logn is in O(n^2) means intuitively that n^2logn grows at most as fast as n^2 -asymptotically (this claim is wrong).

By definition, that means there is some constants c,N such that for each n>N: c*n^2logn <= n^2

Disproving it is very simple by contradiction.
Assume (falsely) the claim is true, and let N,c be our constants:

c*n^2logn <= n^2
c*logn <= 1
logn <= 1/c

But c is constant, and there is some n>N such that logn > 1/c - contradiction.

You can disprove by induction by showing something else, for example - if you show by induction that n! < n^n - you actually disproved the claim n! = n^n

Regarding the big theta, I tried to explain this issue in details in the thread Big Theta Notation - what exactly does big Theta represent?

edited May 23 '17 at 12:31

Community

1
1

answered Feb 06 '14 at 20:52

amit

175,853
27
231
333

1

@C.B. No, that makes no sense, you can have the 'constant' be `2^n` according to this definition (because there is one for each `n`). This is of course - wrong. – amit Feb 06 '14 at 20:55
1

@C.B. Look at the [formal defintiion](http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition) in your own link. `if and only if there exists a positive real number M and a real number x0 such that f(x) <= M*|g(x) for all x>x0.` If there is a 'constant' to each numeber - it implies it is a function of `n` - otherwise there is only one constant. – amit Feb 06 '14 at 20:59
@C.B. It is identical to multiplying g(n) by 1/c instead. The two claims are identical - just an equivalent variation of the same definition. – amit Feb 06 '14 at 21:03
Right I understand they imply the same thing, just meant the formal typical definition was different. We can continue offline if you'd like but I removed my posts as they detracted from the question – C.B. Feb 06 '14 at 21:04
Awesome, thank you for your help! I understand most of what you are saying except for the following: "The claim n^2logn is in O(n^2) means intuitively that n^2logn grows at least as fast as n^2 -asymptotically (this claim is wrong)." I see now that as n gets larger, it grows faster than n^2. You are saying that this means the statement n^2logn=O(n^2) is false right? Meaning that n^2 does NOT grow faster than n^2logn. Sorry, kinda new to all of this. @amit – Nick Feb 06 '14 at 21:30
@NickBlah yes, basically. – amit Feb 06 '14 at 21:45
You are all so awesome! Life savers I swear! – Nick Feb 06 '14 at 22:04

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

I'm taking a course on algorithms right now so I can answer some of these questions, I can answer the rest when I go home and get to take a look at my notes.

For instance I have a statement: n^2logn = O(n^2). Correct me if I am wrong, but this states that n^2 is bigO of n^2logn. Meaning that n^2 grows faster than n^2logn.

You are correct.

Now how would we go about proving this? I assume that I would need to use proof by induction which I have tried to use but got stuck in the process. Could I re-write this statement as n^2logn <= n^2?

Is it possible to disprove something using induction? For example, disproving n!=O(n^n). Or is it valid to disprove the statement by simply showing that an arbitrary value lets say greater than 2 does not satisfy the statement?

I'll get back to you about these in a few hours.

And finally for clarity, bigTheta states that the equations are equivalent when growing correct?

It means that they only differ by a constant. In other words, if you multiply it by a constant it will always be lower than the function it bounds and if you multiply it by another constant it will always be higher than the function it bounds.

Edit:

To test big O, you show mathematically that the function that represents the growth of the algorithm is less than or equal to a constant multiplied by the big O function.

Big Omega is showing the algorithm is greater than or equal to the big Omega function.

Big Theta can be proven in two ways:

Prove both big O and big Omega.
Assume the algorithm is f(n) and the big Theta function is g(n). To prove big theta you have to show that the limit of f(n)/g(n) as n approaches infinity is some constant, i.e., it's neither 0 nor infinity.

I hope that helps. Let me know if you have more questions, I'll be more than happy to help you.

Sorry, I misread the example. I will edit my answer. Thank you for pointing this out. — Leo Jweda, Feb 06 '14 at 20:59
Thank you @LeoJweda your explanation on bigTheta is very helpful! And thank you for taking the time to come back and post more information after reviewing your notes! — Nick, Feb 06 '14 at 21:35
To address @C.B.'s concern, in my course we always say f(n) belongs to O(n). You used f(n) = O(n) which might mean something else. I don't know enough to say for sure what that means. — Leo Jweda, Feb 08 '14 at 22:38

Proving/Disproving BigO, and BigTheta

2 Answers2