Time complexity for a recursive function

Question

I'm a computer science student, I got the final exam next week and I got confused trying to find the time complexity for the following function. Can you explain this to me?

int bss(int n){
    if(n <= 1)
        return n;
    
    return bss(n/2) + bss(n/2);
}

Just try on paper powers of 2. How many calls of bss do you count? — MrSmith42, Jun 04 '21 at 09:36
for bss(1), we call bss 1 times. for bss(2), we call bss 3 times, for bss(4), we call bss 7 times. 15, 31, 63, 127, 255 , 511 ... Do you get an idea? — MrSmith42, Jun 04 '21 at 09:40
From the function you can gather that for every `n > 1`, one call to `bss` spawns two new calls for `n / 2`. The function does no other work, so your recurrence relation is `T(n) = 2T(n / 2)`, and that you can either solve by hand or via [WolframAlpha](https://www.wolframalpha.com/input/?i=T%28n%29+%3D+2T%28n%2F2%29). — Nelewout, Jun 04 '21 at 10:37
Does this answer your question? [Time complexity of a recursive algorithm](https://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm) — Mark Rotteveel, Jun 04 '21 at 15:47

score 2 · Accepted Answer · answered Jun 04 '21 at 15:39

For problems like this, you should figure out the recurrence relation first (by looking at the code), then solve the recurrence relation (using mathematics).

To do step 1, we need to look at each line and see what it contributes to the overall running time T(n) of our algorithm:

int bss(int n){
    if(n <= 1)                        // contributes a constant time a
        return n;                     // contributes a constant time b in the base case only

    return bss(n/2) + bss(n/2);       // contributes a constant time c
                                      // for the two divisions and one addition,
                                      // plus 2T(n/2)
}

Adding up, we get two cases:

n <= 1: T(n) = a + b
n  > 1: T(n) = a + c + 2T(n/2)

To solve this system, we can start writing out terms for values of n. Because we divide n by 2, we might as well choose even n only. Also, it would be nice to have already calculated T(n/2) to calculate T(n); so, we can double our test values of n each time.

n    T(n)
---------
1    a + b
2    a + c + 2T(1) = a + c + 2a + 2b = 3a + 2b + c
4    a + c + 2T(2) = a + c + 6a + 4b + 2c = 7a + 4b + 3c
8    a + c + 2T(4) = a + c + 14a + 8b + 6c = 15a + 8b + 7c
16   a + c + 2T(8) = a + c + 30a + 16b + 14c = 31a + 16b + 15c
...
k    (2k - 1)a + kb + (k - 1)c

Based on the pattern we saw, it seems as though the solution for n = k is (2k - 1)a + kb + (k - 1)c. We can try to verify this by plugging it into our equations:

k = 1: (2k - 1)a + kb + (k - 1)c = a + b = T(1) ... correct
k > 1:

(2k - 1)a + kb + (k - 1)c ?= a + c + 2[(2k/2 - 1)a + (k/2)b + (k/2 - 1)c]
                          ?= a + c + (2k - 2)a + kb + (k - 2)c
                          ?= a + c + 2ka - 2a + kb + kc - 2c
                          ?= -a -c + 2ka + kb + kc
                          ?= (2k - 1)a + kb + (k - 1)c ... correct

So, we have found a valid solution to our recurrence relation. The solution is:

T(n) = (2n - 1)a + nb + (n - 1)c

Rearranging:

T(n) = (2a + c + 1)n - (a + c)

T(n) is the equation of a line.

Time complexity for a recursive function

1 Answers1