0
$\begingroup$

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

$\endgroup$
1

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – johnson
    Commented Dec 25, 2017 at 13:32
  • $\begingroup$ @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)$. $\endgroup$
    – hmakholm left over Monica
    Commented Dec 25, 2017 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – johnson
    Commented Dec 25, 2017 at 13:53
  • $\begingroup$ 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? $\endgroup$
    – johnson
    Commented Dec 25, 2017 at 13:57
  • $\begingroup$ @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$. $\endgroup$
    – hmakholm left over Monica
    Commented Dec 25, 2017 at 15:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .