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?
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?