Whats the time complexity of finding a max recursively

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(nl开发者_JAVA百科gn)?

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)

No, no... you are taking O(1) time for each recursion.

How many are there?

There are N leaves, so you know it's at least O(N).

How many do you need to compare to find the absolute maximum? That's O(log(N)).

Add them together, don't multiply. O(N+log(N)) is your time complexity.