How to calculate the time complexity of the Divide- and-Conquer algorithm?

Question

Here is the Divide- and-Conquer algorithm:

Algorithm: P(a[l … r])
Input: an array a[l … r] of real numbers
begin
if l == r then
    return l
else
    ll = P(a[l ... ⌊(r + l) / 2⌋])
    rr = P(a[⌊(r + l) / 2⌋ + 1 ... r])
    if a[ll] > a[rr] then
        return ll
    else
        return rr
    end if
end if
end

For $n = 2k$ and $k≥1$, the time complexity of the algorithm can be best expressed by what?

Now I have some ideas. First, it recurses using the algorithm. So every recursion has the same time complexity and the total complexity may be n times the base with some addition.

The correct answer is $T(n) = 2T(n/2) + 1$. However, I do not know how to use the given conditions.( $n = 2k$ and $k≥1$) And how to get the answer.

Also, the Big O time complexity is $O(n log n)$, I can understand $log n$ because it needs to divide the sequence into two every time. But why need to time $n$?

Answer 1

The recurrence relation $T(n) = 2T(n/2) + 1$ represents the cost of the algorithm $P(n)$ you defined. We can obtain an upper bound to this relation by expanding the recurrence. We do so for the first few iterations. The first one being:

$$T(n) = 2T\left( \frac{n}{2} \right) + 1$$

The next one being:

$$T(n) = 2\left( 2T\left( \frac{n}{4} \right) + 1 \right) + 1$$

And after one more:

$$T(n) = 2\left( 2\left( 2T\left( \frac{n}{8}\right) + 1 \right) + 1 \right) + 1$$

Which generalises to:

$$ T(n) = \sum_{i = 0}^{\lg n} 2^i = \frac{1 - 2^{\lg n + 1}}{1 - 2} = 2n - 1 $$

And so we conclude:

$$T(n) = O(n)$$

We can verify the bound using the substitution method, if we like.