I learned the following theorem in class: "If $T(n)$ is asymptotically non-decreasing and $f(n)$ is smooth, then $T(n) = O(f(n)|n=b^k, k=integer)$ implies $T(n) = O(f(n))$."

I'm trying to show using a counterexample that this theorem doesn't hold if $f(n)$ is non-decreasing but not smooth. Smoothness means that $f(bn) = O(f(n))$.

From my understanding, the above conditions mean that $f(n)$ must be an exponential. Other than that, how would I go about finding a function that meets the conditions outlined above?

Since this is a homework problem, please don't give an actual function, but instead give a series of steps to take to find the function. Thanks.

  • $\begingroup$ It's hard to give a recipe for solving problems. If there was such a recipe, the work of mathematicians would have a very different character. Problem solving is a creative process. $\endgroup$ – Yuval Filmus Sep 5 '17 at 11:42
  • $\begingroup$ It's OK to answer with how you would go about solving this. I have almost no idea where to start with this. $\endgroup$ – npCompleteNoob Sep 5 '17 at 11:46

As you mention, the function $f(n)$ needs to grow fast, though not necessarily exponentially fast ($n^{\log n}$ also works, for example). Nevertheless, let's take your suggestion $f(n) = 2^n$ for definiteness. Simplifying things a bit, you are looking for a function $T(n)$ such that

  1. $T(n)$ is non-decreasing.
  2. $T(2^k) = 2^{2^k}$.
  3. $T(n)$ is not $O(2^n)$.

To satisfy the third condition, we would like $T(n)$ to be "as large as possible" given the first two conditions.

(a) Find the function $T(n)$ which is "as large as possible" subject to the first two conditions.

(b) Show that it satisfies the third condition as well.

(c) For which functions $f(n)$ does this construction work?

  • $\begingroup$ I wasn't sure what you meant in (c), but your "as large as possible" statement led me to an answer. Thanks. $\endgroup$ – npCompleteNoob Sep 5 '17 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.