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?
-2
$\begingroup$
$\endgroup$
1
$\begingroup$
$\endgroup$
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.
