Consider the following C - function:

double foo(int n){
 int i;
 double sum;
 if(n == 0) return 1.0;
 sum = 0.0;
 for (i = 0; i < n; i++){
  sum += foo(i);
 }
 return sum;
}

Suppose we modify the above function foo() and store the values of foo(i), $$0 \le i \le n$$, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:

Consider the following C - function:

double foo(int n){
 int i;
 double sum;
 if(n == 0) return 1.0;
 sum = 0.0;
 for (i = 0; i < n; i++){
  sum += foo(i);
 }
 return sum;
}

The space complexity of the above function is:

The recurrence equation
T(1) = 1
T(n) = 2T(n - 1)+n, $$n \ge 2$$
Evaluates to

What does the following algorithm approximate?
(Assume m > 1, $$ \in > 0$$)

x = m;
y = 1;
while(x - y > ε){
 x = (x + y) / 2;
 y = m/x;
}
print(x);