Big O Notation - Find a Function That Represents the Statement

Question

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?

Answer 1

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.