3 Solve Problem 146 on Page 208 in the textbook It asks you

3. Solve Problem 1.4.6 on Page 208 in the textbook. It asks you to give the order of growth (as a function of N) of the running times for three code fragments.

Solution

a.) Inner for loop will run n + n/2 + n/4 + ...+ 1 times which is equal to 2n-1 times. Then overall time complexity is O(n).

b.) Inner for loop will run 1 + 2 + 4 + n/4 + n/2 + n/ times which is equal to 2n-1 times. Then overall time complexity is O(n).

c.) Outer for loop runs in O(log n) times and inner loop runs run in O(n) time. Then overall time complexity is O(nlogn).

Hope it helps, do give your response.