1
$\begingroup$

I came across following problem:

Find the time complexity of below recurrence relation:

$T(n)=\begin{cases} & 2T(n/2)+C; & n>1\\ & C;&n=1 \\ \end{cases}$

The solution was given as follows

$\begin{align} T(n) & = C+2C+4C+...nC\\ & = C (1+2+4+...+2^k) \\ & = C \left(\frac{1(2^{k+1}-1)}{2-1}\right) \\ & = C (2^{k+1}-1) \\ & = C (2n-1) \\ & = O(n) \\ \end{align}$

I feel above gives order of return value, but not the order of computation involved.

This function makes two recursive calls with argument $n/2$. Each of these two make another two recursive calls, making total 4, with argument $n/2/2=n/4$. Each of these four make another two recursive calls, making total 8, with argument $n/2/2/2=n/8$. And so on. Thus this form complete binary tree. This tree terminates when $n/2^h=1$. That is, when $2^h=n$.
$\therefore $ Height of binary tree $h=\log_2n$. And the order of computation will be, number of nodes in the complete binary tree for height $h$ which equals $2^{h+1}-1=2^{\log_2n+1}-1=O(2^{\log_2n})$.

Am I correct with this final time complexity and the overall interpretation (of first being the time complexity of the return value and the one which I came up with, the time complexity of computation involved)?

$\endgroup$
1
$\begingroup$

The question is ill-posed. Recurrence relations don't have time complexities.

  • Recurrences have solutions.
  • Algorithms have running times.
  • Problems have time complexities.
$\endgroup$
  • $\begingroup$ "Recurrence relations dont have time complexity" 🤔 Doesnt master theorem give time complexity for the recurrence relation? $\endgroup$ – anir Sep 14 '18 at 19:27
  • $\begingroup$ No, it gives the solution to it. Recurrence relations can be used to describe pretty much anything, just like numbers, so the fact that something is described by a recurrence in no way implies that that thing is a time complexity. Just like something beind described by a number in no way means that that thing is its price. $\endgroup$ – David Richerby Sep 14 '18 at 19:32
  • $\begingroup$ ok seems that I have been ill taught and I need to unlearn certain things. First what is meant by the solution to the recurrence relation? I went through some problems given in Kenneth Rosen's book and it seems that the closed formula for the given recurrence relation is termed as its solution. Thus it seems that master theorem gives asymptotic bound on this closed formula. So solution to recurrence relation is strictly its value obtained by recursively putting values in it and solving. [continued...] $\endgroup$ – anir Sep 14 '18 at 20:14
  • $\begingroup$ [...continued] But if I have been given a recursive function, say in Java, mimicking given recurrence relation, I can relate its return value to the solution of recurrence relation. However, time taken to execute that recursive function is time complexity of that recursive function, and it does not have any parallel to it in recurrence relation. That is, we simply dont have anything in recurrence relations that mimic corresponding code's time complexity. At least, we say so. Am I right? $\endgroup$ – anir Sep 14 '18 at 20:14
  • 1
    $\begingroup$ Right!!!! I guess I understand it now, albeit after some thinking and in fact, it suddenly clicked to me, what you were trying to say, though late...Thanks!!!! (When we are given an algorithm and we try to represent its computation as recurrence relation, then the value of that recurrence relation becomes time complexity or running time of that algorithm. Similarly we can use recurrence relation for representing other stuffs, and for those different stuffs, value of recurrence relation may have different meaning.) $\endgroup$ – anir Sep 15 '18 at 6:22
3
$\begingroup$

Here is a correct version of your original problem.

Find the time complexity of an algorithm which takes $T(n)$ time/operations to finish when the input size is $n$, where $T(n)$ satisfies the below initial condition,

$$T(1) = C$$ and the below recurrence relation, $$T(n) = 2T(n/2)+C\ \text{ if } n>1$$ for some constant $C>0$.

Another correct version would be "Find the asymptotics in term of big $O$ or $\Omega$ notation for the function $T(n)$ that ...".

My answer is based on the above editions of the your original problem.

Your question and much more beyond have been answered in more generality in this reference question and answer and in particular, by the first case of the master theorem.

Assume throughout this answer and the question that $n$ is a positive integer and "/" is the integer division when it is applied to two positive integers as in Python/Java/C/C++/C#. Without these assumptions, $T(1.5)$ and $T(3)$ may not be defined.

Here is a correct computation. Suppose $2^h\le n\lt 2^{h+1}$ for some nonnegative integer $h$. \begin{align} T(n) & = 2T(n/2) + (2^1-1)C\\ & = 2(2T(n/4) +C)+ (2^1-1)C\\ & = 2^2T(n/2^2) + (2^2-1)C\\ & \cdots\\ & = 2^hT(1) + (2^h-1)C\\ & = (2^{h+1}-1)C\\ & = \Omega(n) \end{align} The last equality stands from the fact that $Cn\le (2^{h+1}-1)C\lt 2Cn$.

$\endgroup$
  • $\begingroup$ But thats just return value of recurrence relation, not time complexity of recurrence relation, right? or there is no such thing as time complexity of recurrence relation, at least we say so, even though the code mimicking that recurrence relation can very well have return value as well as time complexity, right? $\endgroup$ – anir Sep 14 '18 at 20:07
  • $\begingroup$ Apparently, you are trying to confusing yourself and me with mingling different concepts. Here is my clarification. If you want to talk about time-complexity, you have to make it clear which procedure/algorithm you are referring to. If given $n$, you just return $(2^{h+1}-1)C$, that is a procedure/algorithm with only several operations, which we will describe as having constant time-complexity or $O(1)$ time-complexity. $\endgroup$ – Apass.Jack Sep 14 '18 at 20:50
  • $\begingroup$ If given $n$, you compute $T(n)$ step by step according to the recurrence relation (in a reasonable way), then that procedure/algorithm would have time-complexity $\Omega(\log n)$. If you know some procedure/algorithm, which will, given $n$, takes $T(n)$ operations to finish, then that procedure/algorithm would have time-complexity $\Omega(n)$. It is in this last case that I understood and answered your question. $\endgroup$ – Apass.Jack Sep 14 '18 at 20:52
  • $\begingroup$ I made three stupid mistakes!!! First, I was ignorant about what should be the exact asymptotic function. It should have been $\Omega$, but out of ignorance I used big $O$. Second $2^{log_2n}$ is indeed $n$. Third, I thought recurrence relation have value and time complexity. But that is not correct. They just have value, as explained by David. The asymptotic bounds of return value of algorithm (if it has any) and time complexity of algorithm has not connection and they can obviously very well be different. Right? $\endgroup$ – anir Sep 15 '18 at 7:38
  • $\begingroup$ Correct, since the return value of an algorithm (if it does return any value) may have nothing to do with the complexity of that algorithm. $\endgroup$ – Apass.Jack Sep 15 '18 at 15:56
0
$\begingroup$

You could also use the Master Theorem

$T(n) = aT(\frac{n}{b})+f(n)$

In your case, a = 2, b = 2 f(n) = $\Theta(1)\therefore$

$f(n) = n^0, 0 < \log_2 2\therefore$ Case 1 and

$T(n) \in \Theta(n^{\log_2 2})= \Theta(n)$

$\endgroup$

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.