Recurrence: space complexity to Tournament Method

Question

Tournament method have this structure to found min and max (function getMinMax):

  mid = (low + high)/2;  
  mml = getMinMax(arr, low, mid);
  mmr = getMinMax(arr, mid+1, high);  

  /* compare minimums of two parts*/
  if (mml.min < mmr.min)
    minmax.min = mml.min;
  else
    minmax.min = mmr.min;     

  /* compare maximums of two parts*/
  if (mml.max > mmr.max)
    minmax.max = mml.max;
  else
    minmax.max = mmr.max;

Time complexity is , but how can I found the space complexity? You stack values, plus values, plus values... until values. So (log n times). . That's right?

Answer 1

First of all, when talking about space complexity, we need to make sure what exactly we are counting. There are two main issues:

1. Are we counting the space taken by the input?

2. How much space does a variable like mid or mml take? How much space does the return address take?

Regarding the first issue, usually we're not counting the space taken by the input; this space should be accounted for in the procedure creating the array. This convention is important in complexity theory for handling space complexity classes with small working space, and also makes practical sense.

Regarding the second issue, we actually have two kinds of variables here:

1. Addresses – the return address, mid, and perhaps other temporary values.

2. Array elements – the two components of mml and mmr.

The usual convention counts machine words rather than bits. Without explaining what exactly machine words are, it is usually assumed (and practically justified) that addresses take $O(1)$ machine words.

Regarding array elements, it depends on the type of the array. Here presumably the array elements are machine integers of machine floating points, and so they also take $O(1)$ machine words.

---

Having clarified these issues, let us get back to the algorithm. When analyzing the time or space complexity of an algorithm, we usually measure the complexity with respect to the input size $n$ (in machine words). In this case, we can identify the input size with the size of the array (measured in number of elements), although the input is actually a bit larger.

Suppose for simplicity that $n$ is a power of 2, say $n = 2^m$. When we trace the execution of the algorithm, we discover recursive calls for the following subarrays are made:

• $A[0,2^m)$
• $A[0,2^{m-1})$
• $A[0,2^{m-2})$
• $\ldots$
• $A[0,1)$

(Here $A[a,b)$ consists of the elements $A[a]$ up to $A[b-1]$.) After the call on $A[0,1)$ executes, we get another call to $A[1,2)$, and so on and so forth.

At the particular point in time illustrated in the call stack above, the call stack is $m+1$ levels deep, and so the stack consists of $\Theta(m)$ machine words. That already shows that the algorithm requires $\Omega(m)$ space. Since the space taken by local variables is part of the call stack, the memory usage at any point in time is big Theta of the depth of the call stack (since each level requires $\Theta(1)$ machine words). It's not hard to check that the call stack never gets more than $m+1$ levels deep, and so the space is $\Theta(m)$.

When $n$ is not a power of 2, a very similar analysis shows that the space usage of the algorithm is $\Theta(\log n)$.