Solve: T(n) = T(n/2) + n/2 + 1

asymptotic-complexity, computer-science, computer-science-theory, time-complexity

Solution

The `while` is executed in about `n/2` time.

The recursion is executed passing as `n` a value that is about half of the original `n`, so:

n/2 (first iteration)
n/4 (second iteration, equal to (n/2)/2)
n/8
n/16
n/32
...

This is similar to a geometric serie.

Infact it can be represented as

n * (1/2 + 1/4 + 1/8 + 1/16 + ...)

So it converges to `n * 1 = n`

So the O notation is O(n)

Problem

I struggle to define the running time for the following algorithm in O notation. My first guess was O(n), but the gap between the iterations and the number I apply isn't steady. How have I incorrectly defined this? ``` public int function (int n ) { if ( n == 0) { return 0; } int i = 1; int j = n ; while ( i < j ) { i = i + 1; j = j - 1; } return function ( i - 1) + 1; } ```

Original source