# Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?

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?

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$$).

• 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})$? Mar 7, 2021 at 6:42
• A recurrence doesn’t have a runtime. Mar 7, 2021 at 6:43
• 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})$? Mar 7, 2021 at 7:44
• 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$. Mar 7, 2021 at 7:49
• 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? Mar 7, 2021 at 9:41

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.

• 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. Mar 7, 2021 at 10:50