How do I prove n^3.5 is not O(n^3)?
I am doing this for my algorithm class.
It says I need to prove it using proof by Contradiction!
121 Answer
Let us use the definition of big O.
f(n) = O(g(n)) means that there exists a constant C and a value n0 such that for every n > n0, |f(n)| <= C |g(n)|.
We want to prove that for f(n) = n3.5 and g(n) = n3 by contradiction. So, assume that there exists such constant C that |n3.5| <= C |n3| holds. Sure, it's false, and here's why: take, for example, n = C10, and see that |C35| <= C |C30|, which is the same as to say that C35 <= C31. And that's obviously false for any C > 1. For any larger n (recall we need n > n0), this also obviously does not hold.
