1. What is the time complexity T(n) of the nested loops below? For simplicity,you may assume that n is a power of 2. That is, n = 2^k for somepositive integer k.

i = n;

while (i >= 1) {

j = i;

while (j

// Needs (1).

j = 2 * j;

}

i = |i/2|;

}

}

2. Show the correctness of the following statements.

a. lg n O (n)

b. n O(n lg n)

c. n lg n O (n^2)

d. 2^n (5^ln n)

e. lg^3 n o (n^0.5)