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?

Answer 1

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?

Answer 2

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:

1. Prove both big O and big Omega.

2. 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.