# Find non-smooth function that meets conditions

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.

• 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. – Yuval Filmus Sep 5 '17 at 11:42
• It's OK to answer with how you would go about solving this. I have almost no idea where to start with this. – 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?

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