I think I solved this recurrence relation problem but I am not sure if my answer is correct. Can you please help me?
n >= 1 is a power of 2 integer
T(1) = 0
T(n) = T(n/2) + 100
My approach
T(2) = T(1) + 100 = 100
T(4) = T(2) + 100 = 200
T(8) = T(4) + 100 = 300
T(16)= T(8) + 100 = 400
I guessed the solution to be 100 * Log(n)
By induction I attempted to prove it
T(n) = 100 log(n/2) + 100
= 100 log(n) + 100
Is this correct?