Cheap and Secure Web Hosting Provider : See Now

[Answers] Big O Notation - Find a Function That Represents the Statement

, , No Comments
Problem Detail: 

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?

Asked By : Daniel Gagnon

Answered By : Alex Meiburg

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18794

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback