# Finding running time

Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne.

Give a formula to predict the running time of a program for a problem of size N when doubling experiments have shown that the doubling factor is $2^b$ and the running time for problems of size N0 is T.

$$\frac{T(2N)}{T(N)}=2^b.$$

$$T(N_0)=T.$$

I am not sure how to proceed after that.

## 1 Answer

Instead of solving the question for you, let me show you what steps you need to take in order to solve this problem on your own.

Suppose that $T(1) = T_0$ and $T(2n) = C T(n)$ for all $n$.

• What is $T(2)$? What is $T(4)$? What is $T(8)$? What is $T(2^k)$?

Now suppose that $T$ is monotone: $T(n_1) \leq T(n_2)$ whenever $n_1 \leq n_2$.

• If $2^k \leq n \leq 2^{k+1}$, what can you say about $T(n)$?
• Can you now deduce the asymptotic rate of growth of $T(n)$ for arbitrary $n$?
• I can guess that it is $(N/N_0)^b$ but not too sure how to write a sequence of equations to show it. – johnson Dec 25 '17 at 15:09
• Try working on it for a few hours. That's the only way to learn. – Yuval Filmus Dec 25 '17 at 15:11
• You asked "what can you say about T(n)?". I'm not sure what else to say besides it is $\ge T(2^k) and \le T(2^{k+1})$ – johnson Dec 25 '17 at 15:26
• I'm not sure how to find the answer for n which is not a power of 2 – johnson Dec 25 '17 at 15:28
• It's in fact impossible, given just your recurrence formula. But you can find the asymptotic rate of growth ("big Theta", which is a stronger form of "big O"; see cs.stackexchange.com/questions/57/…) assuming that $T$ is monotone. – Yuval Filmus Dec 25 '17 at 15:31