# Computing ratios of running times

Apologies for this simple question. 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.

Edit:

I know that intuitively it would be $\bigl({\frac{N}{N_0}}\bigr)^bT$ but I am not sure how to write it out mathematically

Hint: For a given $N$ you have $\log_2(N/N_0)$ doublings of $N$. This corresponds to multiplying $T$ by $2^b$ that many times, giving $$T(N) = T \cdot (2^b)^{\log_2(N/N_0)}$$ Now use power and logarithm rules to simplify the right-hand side of this.
If this is too hand-wavy for your context, you can prove that the above relation for $N$ of the form $2^k N_0$ by induction on $k$. When $N$ does not have precisely this form, the recurrence strictly speaking doesn't give you all the information you need, but if you have other reasons to expect that $T(\cdots)$ is increasing, knowing its value at $2^k N_0$ will be sufficient to speak about its asymptotic behavior.
• For a given $N$ you have $\log_2(N/N_0)$ doublings of $N$. What does this mean? If N is a power of 2, you have $log_2(N)$ doublings of N. So how does $N_0$ enter into things Commented Dec 25, 2017 at 13:32
• @johnson: The base case of the OP's recurrence is $N_0$, and the number of doublings from there up to $N$ is $\log_2(N/N_0)$. Commented Dec 25, 2017 at 13:43
• I can understand how things work for powers of 2 but not otherwise. E.g. $N=16,N_0=2$. Then $N=2^3N_0$.$log_2(N/N_0)=3.$ But what if we are not working with powers of 2. Commented Dec 25, 2017 at 13:53
• I've thought for a while and could think of this. $8=2^1*2^1*2^1=2^3, 9=2^1*2^1*2^1*2^y$. Does this mean that we will definitely be able to find a y such that this holds? Commented Dec 25, 2017 at 13:57
• @johnson: See the second part of the answer -- for $N/N_0$ not a power of $2$, your recurrence alone does not force any particular value of $T(N)$. But if $T$ is nondecreasing, you can still at least know that $T(N)$ is within a factor of $2^b$ of $(N/N_0)^bT_0$. Commented Dec 25, 2017 at 15:18