1

I cannot solve this time & space complexity in C that I encountered. This is the question:

Calculate the time & space complexity of the function f3:

double g3(double n) 
{
    if (n<=1)
    return 2;
    double temp = g3(n/2);
    return temp*temp;
}
double f3(double n){
    return g3(g3(n));
}

I calculated that the time complexity of g3 is O(logn) and its return value is 2^2^n-1 (for n >= 1). From this point on I have no idea what to do.

Please explain the way you solved it. Thank you very much :)

Gil Levin
  • 41
  • 5
  • 2
    You could at least make _some_ effort to solve it yourself, show your answer or where you got stuck, and ask for help or confirmation from there. I doubt many people just want to do your homework for you for free. – Useless Jan 29 '19 at 10:05
  • Thank you for the suggestion :) – Gil Levin Jan 29 '19 at 10:22

1 Answers1

1

Time:

You've worked out that g3(n) recurses about log_2 n times, due to the n/2 at each recursive call. This also means that the base case (2) will be squared roughly log_2 n times before it's finally returned.

The return value of g3(n) is then ~2^(2^log_2 n) which simplifies to ~2^n.

To work out what is happening in g3(g3(n)), we can work out what happens in g3(k) where k = 2^n as returned by the inner g3(n) call. You already know that g3(k) recurses log_2 k times just like the inner call. So, if we replace k with our inner result we get log_2 (2^n) recursive calls which simplifies to just n. So the outer call in g3(g3(n)) recurses n times.

Now we can work out the total time complexity. First, it takes O(log n) steps to work out g3(n). Second, it takes O(n) steps to work out g3(2^n). Therefore, the total time complexity for g3(g3(n)) is inner + outer or O(log n) + O(n) where the O(n) dominates.

Therefore, f3(n) takes O(n) time.

Space:

To work out how much space is used, we need to consider

  1. Where in our program is memory being allocated?
  2. What is the maximum amount of memory allocated as a function of n?

We don't have any arrays taking up memory, so our biggest concern is the memory allocated for the stack frame of each function call. Each time you call g3(n) there is some memory allocated for storing local variables and other data. Each time g3(n) returns, that memory is released and can be used for other things.

What is the maximum number of stack frames allocated at the same time during execution? If you can answer this, then you can work out the number of frames allocated as a function of n and, therefore, the space complexity. I'll leave the final result for you to discern.

If you can't solve something, break it down into smaller problems that you can solve. Every time you solve a small problem, look at how you can use the result to simplify the big problem.

puqeko
  • 321
  • 2
  • 9