TITLE: Recurrence Relation (asymptotic notation)
QUESTION [0 upvotes]: The question is - Solve the recurrence: T(n) = T(n/2) + O(n) and T(1) =c, where c is constant.
At first I thought, if we replace the RHS repeatedly by the recurrence, then, we will end up at - $T(n) = c+ O(\frac n {2^{(k-1)}})$ + $O(\frac n {2^{(k-2)}})$ + ... + $O(n)$. Since $O(n/r) = O(n)$ for any constant r, thus each term of the rhs sum is O(n). Again, $O(f(n)) + O(g(n)) = O(max(f(n), g(n)))$, thus $T(n)$ will be $O(n)$.
But again, I thought, the number of summands in the RHS is $\log_2 (n)$, thus $T(n) = \log_2 n * O(n) = O((\log_2 n)* n)$. Now, I am confused between these two thoughts. Please someone guide me which one is the right approach and where I am doing the mistake.
It will be also helpful if anyone suggest how can to apply Master theorem in the problem. Any help is highly appreciated.

REPLY [1 votes]: According to the Master Theorem, your problem has the form:
$$
T(n)=1\cdot T\left(\frac n2\right)+f(n)
$$
with $f(n)=\mathcal O(n^1)$ meaning $c=1$ and the critical exponent equal to $c_{crit}=\log_2(1)=0$. Since $c>c_{crit}$ and we do not know $f$ to be lower bounded this does not directly fit any of the cases in the theorem.

Let us instead do the analysis from the bottom:
Since $f(n)=\mathcal O(n)$ there exists $A,N$ such that:
$$
f(n)\leq An\quad\text{for }n\geq N
$$
Furthermore, we may find an upper bound $B$ for the earlier values of $T(n)$:
$$
T(n)\leq B\quad\text{for }n<N
$$
Thus given $n\geq N$ we have:
$$
\begin{align}
T(n)&=T\left(\frac n2\right)+f(n)\\
&\leq B+A\frac n{2^t}+...+An\\
&=B+An\left(1+\frac12+...+\frac1{2^t}\right)\\
&\leq B+2An
\end{align}
$$
This clearly shows that $T(n)=\mathcal O(n)$. The number of terms turns out to be irrelevant.
{"set_name": "stack_exchange", "score": 0, "question_id": 4385226}