1
$\begingroup$

In my analysis of algorithms class we were given the following recurrence relation:

\begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\ 2T\left(\displaystyle\frac{n-1}{2}\right), &n \ \mbox{is odd number}& \end{cases} \nonumber \\ T(1) &=& 1 \end{eqnarray}

I have proved by iteration (expand) that when $n = 2^k$ (always the even case), $T(n) = O(\log{n})$; when $n = 2^{k+1}-1$ (always the odd case), $T(n) = \Omega(n)$.

Is this actually possible? After looking at some other posts, I am thinking this is possibly because the $\Omega(n)$ obtained here is the lower bound runtime of the worst case scenario, and the $O(\log{n})$ is the upper bound runtime of the best case?

Am I confusing something? Or is there any other conclusion can be drawn from the result that $T(n) = O(\log{n})$ and $T(n) = \Omega(n)$ for the recurrence?

$\endgroup$
0
$\begingroup$

Your recurrence satisfies neither $T(n) = O(\log n)$ nor $T(n) = \Omega(n)$.

What does hold is that there exists an infinite sequence of values $n_k$ such that $T(n_k) \leq C\log n_k$, and another infinite sequence of values $m_\ell$ such that $T(m_\ell) \geq c m_\ell$, where $C,c>0$ are some constants.

The definitions of big O and big Omega require such inequalities to hold for all large enough $n$, rather than for infinitely many values.


A similar situation is that of partial limits and limits superior and inferior. Consider the sequence $\sin n$ (where the angle is measure in radians). For each $x \in [-1,1]$, we can find an infinite sequence $n_k$ such that $\sin n_k \to x$. These are the partial limits of the sequence. The limit superior of the sequence is $1$, and its limit inferior is $-1$.

Similarly, in your case, $\Theta(\log n)$ and $\Theta(n)$ are "partial asymptotic limits", in the sense that there is an infinite sequence $n_k$ such that $An_k \leq T(n_k) \leq Bn_k$ for some $A,B>0$, and another infinite sequence $m_\ell$ such that $C \log m_\ell \leq T(m_\ell) \leq D \log m_\ell$ for some $C,D>0$. The "asymptotic limit superior" is $O(n)$, since $T(n) = O(n)$ but $T(n)$ is not $O(f(n))$ for any $f(n) = o(n)$. Similarly, the "asymptotic limit inferior" is $\Omega(\log n)$, since $T(n) = \Omega(\log n)$ but $T(n)$ is not $\Omega(g(n))$ for any $g(n) = \omega(\log n)$.

(Showing that $T(n) = O(n)$ and that $T(n) = \Omega(\log n)$ requires an argument.)


A sequence such as $\sin n$ has no limit. Similarly, $T(n)$ has no "asymptotic limit", that is, there is no "nice" function $h(n)$ such that $T(n) = \Theta(h(n))$ (we can define "nice" in various ways, for example a logarithmico-exponential function, that is, a function which can be expressed using arithmetic operations, $\log$ an $\exp$).

$\endgroup$
8
  • $\begingroup$ I got the "limits" idea on the $\sin{n}$ analogue but am not quite sure when applied to the recurrence. So instead of numerical values, the limits here are the Landau notations, that I could possibly also find another infinite sequence $n_k$ s.t. $\Theta(\sqrt{n})$ being one of the "partial asymptotic limits" of the recurrence? Can I say for this recurrence, $O(n)$ is the tight upper bound and $\log{n}$ the tight lower bound? Or can I say, if $T(n)$ represents the runtime, this recurrence's worst case runtime is $\Theta(n)$ or $O(n)$, and best case runtime $\Theta(\log{n})$ or $O(\log{n})$? $\endgroup$
    – bubblessss
    Mar 7 at 6:42
  • $\begingroup$ A recurrence doesn’t have a runtime. $\endgroup$ Mar 7 at 6:43
  • $\begingroup$ I just had a look again at my textbook. Will it be correct to say instead that, $T(n) = O(n)$ and $T(n) = \Omega(\log{n})$, with $O(n)$ and $\Omega(\log{n})$ being tight upper bound and tight lower bound, respectively? Or, the recursive algorithm with this recurrence relation, has worst case running time $\Theta(n)$ or $O(n)$, and best case running time $\Theta(\log{n})$ or $O(\log{n})$? $\endgroup$
    – bubblessss
    Mar 7 at 7:44
  • $\begingroup$ Worst-case and best-case running times are functions of $n$. They refer to the variety of different inputs of length $n$. It's not about different values of $n$. $\endgroup$ Mar 7 at 7:49
  • $\begingroup$ Thanks for the clarification! I have one more question. How did we come to the conclusion that $O(n)$ is the "asymptotic limit superior" while $\Omega(\log{n})$ is the "asymptotic limit inferior"? Because we just managed to find two infinite sequences which can be bounded by $\log{n}$ and $n$ individually, there may exist some other infinite sequences that are bounded by other $f(n)$. Is there a way to prove it? $\endgroup$
    – bubblessss
    Mar 7 at 9:41
0
$\begingroup$

You calculated “Big-Theta for n = power of two - 1”. That’s not a useful thing. Try calculating T(n) for n = (4^k - 1) / 3 and be surprised. (Write n down in binary first). Or n = 3 * (8^k - 1) / 7 where T(n) ≈ n^(2/3).

You found the values for a good case and for a bad case. You’ll have to prove they are lower and upper bound.

$\endgroup$
1
  • $\begingroup$ I don't quite understand what does "Write n down in binary first" mean and how to go from there. But I managed to prove by induction that when $n = \frac{4^k-1}{3}$, $T(n) = \Omega(\sqrt{n})$. I think this makes $\Theta(\sqrt{n})$ one of the "partial asymptotic limits" as mentioned by another user in this question. It is interesting to know the example sequences you've given. $\endgroup$
    – bubblessss
    Mar 7 at 10:50

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.