Example 2: Binary Search

Let's take the example of binary search for finding a value in a sorted array. We'll look at both the iterative and recursive solution.

Iterative Solution

1Function: binarySearch(arr, n, value)
2Returns:  True/False
3
4Method:
5lower = 0
6upper = n-1
7found = false
8while(lower<=upper and !found)
9{
10	mid = (lower+upper)/2
11	if arr[mid] < value
12		lower = mid+1
13	else if arr[mid] > value
14		upper = mid-1
15	else
16		found = true
17}
18return found

The space complexity of the iterative solution can easily be computed as follows: 1. Input space: O(n) 1. Auxiliary space with variables (n, value, lower, upper, found, mid): O(1) 1. Overall space complexity counting the input and auxiliary space: O(n)

Recursive Solution

Given below is the pseudo-code for the recursive version of binarySearch:

1Function: binarySearchRecursive(arr, value, lower, upper)
2Returns:  True/False
3Call this function for array size n using: binarySearchRecursive(arr, value, 0, n-1)
4
5Method:
6if lower >= upper
7	return false
8mid = (lower+upper)/2
9if arr[mid] == value
10	return true
11if arr[mid] < value
12	return binarySearchRecursive(arr, value, mid+1, upper)
13
14return binarySearchRecursive(arr, value, lower, mid-1)	

Here, the recursive calls generate the activation stack. Each record on the stack holds a separate copy of the variables lower, upper, mid and value. The array can be passed by reference so a separate copy of the array is not created for each function call. As we can have O(log(n)) calls to binarySearchRecursive function, the space complexity of the recursive version should include the O(log(n)) auxiliary space. Hence, the overall space complexity is:

1. Input space: O(n)
2. Auxiliary space for recursive calls involving O(log n) records created on stack: O(log n)
3. Overall space complexity counting the input and auxiliary space O(n)