Imagine you had an algorithm with runtime T$($n$)$ satisfying the recursion

T$($n$)=$ T$($n$/2)+1($and T$(1)=1).$ You have probably seen the binary search

algorithm that exactly obeys that recursion. Prove that T$($n$)=$ O$($log n$).$ Then,

imagine another algorithm with Q$($n$)=$ Q$($n$/2)+$n $($and Q$(1)=1).$ Prove that

Q$($n$)=$ O$($n$)\mathrm{.}2$