Prove $T(n)\leq T(\lfloor n/2\rfloor) +n=O(\log_2n)\forall n\geq 2$

Question

$\forall n\geq 2(T(n)\leq T\left(\lfloor n/2 \rfloor\right) +n)=O(\log_2n)$

Hi guys, I am stuck in an assignment question

I have proved i, ii, iii by myself.

1. 1.a.ii has provided all sufficient conditions for 1.a.iii to be true.
2. The second condition if $n = 2^k$ then $S(n) = O(k)$ is proved by 1.a.i.
3. The first condition, which asks for a non-decreasing function, tortured me for an hour and ten minutes.
4. I tried to connect the dots between 1.a.iii with non-decreasing function and tried induction, strong induction or $\max(n) = T(n)$ but no matter how hard I try, 1aiii is reducing the function but not extending it and I have been chasing circles for an hour already.

Please, could someone shed some light? Is 1aiii really about non-decreasing function? If not, how to prove $T(n)$ is non-decreasing? And the last thing, is $\max(n)=T(n)=T(\lfloor n/2\rfloor)+n$ due to the definition?

Answer 1

I think here is the answer

$S(n)=max_{1\leq j\leq n}T(n)$is a nondecreasing function.

Why? Well, because $max_{1\leq i\leq n+1}T(n)\geq max_{1\leq i\leq n}T(n)\rightarrow S(n+1)\geq S(n)$

$S(n)$meets the requirement of equation 1

Why? Cause I proved in 1aiii that $S(n)\leq S(\lfloor n/2\rfloor)+c$.

By 1aii,

1. $S(n)$ is nondecreasing.
2. $S(n)$ meets the requirement of equation 1
3. Therefore, $S(n)=O(log_2(n))$

But here's the catch!

$$\exists c\geq1,n\geq n_0 s.t. T(n)\leq max_{1\leq i\leq n}T(n)\leq clog_2n$$ $$T(n)=O(logn)\forall n$$