Writing a function for F(n)=0.5F(n-1)

Question

let F(n)=0.5F(n-1) and F(0)=1

a. write a function fun1, a recursive function to evaluate the n's term

b. write a function fun2, a non recursive function to evaluate the n's term

c. what is the time complexity of fun1 and from which n term it will be better to use fun1 vs fun2 regarding space complexity

In general the function evaluate the n term of the sequence {1,1/2,1/4,1/8,...}

a.

 double fun1( int n ){
    if (n == 0)
        return 1;
    else
        return 0.5*fun1(n-1);
}

b.

double fun2( int n ){
    double sum = 1, i;
    for (i=0 ; i < n; i++)
        sum=sum*(0.5);
    return sum;
}

c. Intuitively and mathematically using the sum of geometric sequence we can show that it is O(n)

1. is there another way?
2. how to address space complexity?

Answer 1

While your versions of fun1 and fun2 are of different space complexity, their time complexity is O(n).

However, the non-recursive function can also be written as:

#import <math.h>

double fun2(int n) {
    return pow(0.5, n);
}

This function is of space and time complexity O(1) and will be more efficient for most n (probably n > 5).

As for the original question: It's very tricky as it depends on the compiler optimization:

A naive implementation is of fun1 is of space complexity O(n) as a call of fun1(n) will have a recursive depth of n and therefore requires n call frames on the stack. On most systems it will only work up to a certain n. Then you get a Stack Overflow error because the stack has a limited size.

An optimizing compiler will recognize that it's a tail-recursive function and will optimize it into something very close to fun2, which has a space complexity of O(1) as it uses a fixed number of variable with a fixed size independent of n and no recursion.

Answer 2

I understand that this is a homework question so I will not refer anything about compiler optimizations and tail recursion since this is not property of the program itself but it depends on the compiler if it will optimize a recursive function or not..

Your first approach is clearly O(n) since it calls recursively f1 and all it does a multiplication.

Your second approach is also clearly O(n) since it is just a simple loop. So as for time complexity both are the same O(n)

As for space complexity fun1 needs n function records so it is O(n) space complexity while fun2 only needs one variable so it is O(1) space complexity. So as for space complexity fun2 is a better approach.