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