Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)

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: