There's an f(n) such that f(n) != O(f(n/2))

so by the definition of big O notation:
for f(n) = n^2 the statement is false, because there is a constant c such that n^2 = c*(n^2/2)

Which f(n) will work?
My guess is f(n) = 2. is that correct?


f(n) = 2 does not work, no, because there is a constant c such that 2 = c*(2/2), namely c = 2. The function you're describing is a constant function, which is normally written O(1).

Any function of the form f(n) = a * n^b will not work (with the constant c = 2^b), but exponential functions will.

If we let f(n) = k^n, then we have O(f(n/2)) = c * f(n/2) = c * k^(n/2) = c * sqrt(k^n). Then we could find

f(n) < O(f(n/2))
k^n < c * sqrt(k^n)
sqrt(k^n) < c

By choosing n large enough, we could always invalidate this inequality; so there is no such c.

To briefly cover some other functions, anything of the form: f(n) = n! f(n) = k^(n^n) or f(n) = (a^n) / (n^b) will work, anything of the form f(n) = n^a * (log(n))^b f(n) = n^a */ (log(n))^b will not work.

anything "approximately" exponential or faster will work, anything "approximately" polynomial or slower will not.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.