Solution for the recurrence algorithm-CodePudding

How is T(n) = 4T(n/2 2) n solved ?
I found a solution in a website: https://ita.skanev.com/04/04/03.html
I don't understand it.
Is T(n) = 4T(n/2 2) n equivalent with T(n) = 4T(n/2) (n 2) ?

CodePudding user response：

Execute sub parentheses first along with below priority, you will find answer by yourself.

operator : priority
/        : 0
*        : 1
         : 2
-        : 3

CodePudding user response：

I think this is just Case 1 in the Master Theorem. You can read the theorem here https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms).

Basically, in your problem, a = 4, b = 2, and c = 1. So, we have log_b(a) = 2 > c. Therefore T(n) = Theta(n^2).