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

Question

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;
}

Welldressed

To be exact, bit-O is for upper bounds, so there are many possible answers. For example it is true, but rather misleading, to say that this algorithm is O(n*n). When possible, it's usually better to use big-Theta to state running times. The analysis in the accepted answer is equally valid for big-Theta. – Whole

Answer 1

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)

Reese

Answer 2

Another approach is to write it down as T(n) = T(n/2) + n/2 + 1.
The while loop does n/2 work. Argument passed to next call is n/2.

Solving this using the master theorem where:

• a = 1
• b = 2
• f = n/2 + 1

Let c=0.9
1*(f(n/2) + 1) <? c*f(n)
1*(n/4)+1 <? 0.9*(n/2 + 1)
0.25n + 1 <? 0.45n + 0.9
     0    <  0.2n - 0.1 

Which is:

T(n) = Θ(n)

Cordon