f(n) such that
f(n) != O(f(n/2))
so by the definition of big O notation:
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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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)
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.