Finding time and space complexity of this program

user_14854871 0
Viewed 64
    def g3(n):
        s = 0
        i = 1
        while i < n:
            i *= 2
            s += i
        return s
    
    def f3(n):
        s = []
        i = 2
        while (i < n):
            s.append(g3(i))
            i *= i
        return s

I am trying to calculate the time and space complexity of the function f3, I am reaching some wrong answer, and I can't get where is my mistake, the final answer is time complexity: O(log(n)), space complexity O(log(log(n))).

My work:
First I decided to calculate time complexity of function g3 since f3 calls it inside the loop. the values of i are 2^k after k iterations and it stops whenever 2^k >= n which means k=log(n). so now I know that time complexity of g3 is log(n).
Moving on to f3 inside the loop, the values of i are 2,4,16,256 or in another words 2^(2^k) and it stops whenever 2^(2^k) >= n so we get k = log(log(n)).
Now in order to calculate the whole time complexity of f3, I know that the function f3 calls g3 log(log(n)) times in total. So the time complexity should be something like this: 

[log(2^(2^0))+log(2^(2^1))+...+log(2^(2^(log(log(n)))]*log(n)

Note that all of them are multiplied by log(n) since each call iterates log(n) times in g3 (or atleast I understood it like that).
Now I got stuck here as I feel I went so far and made some mistakes, and I can't figure out the total time complexity and can't see it being O(log(n)), I would really appreciate any help or feedback.
Thanks in advance to everyone!

space-complexity time-complexity python
1 Answers

You had the right reasoning until the very moment when you computed the complexity. Each call does not iterate log(n) times in g3 but log(2^(2^k)) at the k-th iteration.

Let us take one iteration k of f3. This iteration has complexity log(2^(2^k))). Since k goes from 1 to N=floor(log(log(n))), the total complexity is the sum from k=1 to N of the log(2^(2^k)). Using the property log(a^b) = b*log(a), this gives us a time complexity equal to the sum of 2^k from 1 to N (getting rid of multiplicative constants), which gives us, once again getting rid of multiplicative constants, a time complexity in O(2^N). Since N=log(log(n)), we finally get a time complexity of 2^(log(log(n))). Since log refers to the base-2 logarithm here, this finally fives us a complexity of O(log(n)).

Concerning the time complexity, you store O(log(log(n))) times a value, which gives a space complexity of O(log(log(n))).

Tristan_Nemoz_114827280
Related