Whats the time complexity of finding a max recursively

Question

I just wanted to make sure I'm going in the right direction. I want to find a max value of an array by recursively splitting it and find the max of each separate array. Because I am splitting it, it would be 2*T(n/2). And because I have to make a comparison at the end for the 2 arrays, I have T(1). So would my recurrence relation be like this:

T = { 2*T(n/2) + 1, when n>=2 ;T(1), when n = 1;

and and therefore my complexity would be Theta(nlgn)?

Answer 1

The formula you composed seems about right, but your analysis isn't perfect.

T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...

For the i-th iteration you'll get:

Ti(n) = 2^i*T(n/2^i) + i

now what you want to know for which i does n/2^i equals 1 (or just about any constant, if you like) so you reach the end-condition of n=1. That would be the solution to n/2^I = 1 -> I = Log2(n). Plant it in the equation for Ti and you get:

TI(n) = 2^log2(n)*T(n/2^log2(n)) + log2(n) = n*1+log2(n) = n + log2(n)

and you get T(n) = O(n + log2(n) (just like @bdares said) = O(n) (just like @bdares said)