CMI2021-B: 7

Question

Consider the function $\textsf{foo}$ and $\textsf{bar}$ described in pseudocode below, where $/ /$ denotes quotient (integer division) and $\%$ denotes remainder.

int foo (int n) {
    int i = 1;
    while (bar (i) < n){
        i = 2* i;
    }
    return (i);
    }
    
    int bar (int n){
        if (n == 0){
            return (1);
            }
            int x = bar(n // 2);
            if (n % 2 == 0) {
                return (x*x);
            } else {
                return (2*x*x);
            
        }
}

1. What function does $\textsf{bar (n)}$ compute? Justify your answer.
2. If $\textsf{foo (n)}$ compute $\textsf{x}$, how do $\textsf{n}$ and $\textsf{x}$ relate to each other. Justify your answer.
3. How many recursive calls to $\textsf{bar}$ and made in computation of $\textsf{foo(100)}?$