$$T(n) = 2T(n/2) + \Theta(n), n > 1$$$$T(n) = \Theta (1), n \le 1$$$$G(n) = G(\lfloor n/2 \rfloor) + G (\lceil n/2 \rceil) + \Theta(n), n > 1$$$$G(n) = \Theta (1), n \le 1$$Prove $T(n)$ and $G(n)$ have the same asymtotic running time.I tried using the sandwich theorem but got nowhere. Please be really explicit and show all your steps in your answer. Thank you.
Compare speed of two algorithms?
asymptotics;recurrence relation