Time complexity for recursive binary search that also prints current subarray

Question

Find the total running time of the following code in big O notation. The input array is sorted with size n.

int print (int array[], int low, int high, int x) {     
    int mid = (high + low) / 2;
    if (low > high)
        return -1;      // cannot find x in the array
    if (array[mid] == x)
        return mid;     // x is found
    if (array[mid] > x) {
        for (int i = low; i < mid; i++)
            printf("%d ", array[i]);
        return print(array, low, mid – 1, x);
    }
    if (array[mid] < x) {
        for (int i = mid + 1; i <= high; i++)
            printf("%d ", array[i]);
        return print(array, mid + 1, high, x);
    }
}

The recursive part is the same as binary search, so I know the time for that part is O(log n). The program prints out every element for the subarray that may contain the query x, so can I say the running time for that line is O(n)? And the total running time of the code is simply O(n)?

Is the recursive part O(log n) affecting the total running time?

Answer 1

The output concerns the subarray that is about to be used for the recursive call. So each output concerns the half of the current window, which halves at each recursive call. This is a geometric series, and the sum has a closed formula, which in this case is bounded by 𝑛 (as we start the series with 𝑛 /2). So in total, O(𝑛) array values are printed (and as many spaces).

There are now two scenarios to distinguish:

1. This is pseudocode and there is no limit on how large the integers are: in that case printing a single value is not O(1): it takes O(1) time to print one digit. It takes more time to print an integer that has 50 digits than an integer with just 2 digits. So then the time complexity is O(𝑑𝑛), where 𝑑 is the average (or maximum) number of digits for an integer in the input array. We could also say it is O(𝑛log𝑚), where 𝑚 is the maximum value in the array, or the negated minimum value in the array, whichever is greater (as there could be negative values).

   For example, if the array would be equal to [1,2,3,..,𝑛] then 𝑚=𝑛, and the complexity O(𝑛log𝑛).

2. The int data type represents a fixed size data type (like 64-bit), and so we know the decimal representation of such integers has a fixed ceiling on the number of digits they can have. In that case the effort of printing an integer is O(1), and the overall complexity is O(𝑛).