Question

1.4.6 Give the order of growth (as a function of n) of the running times of each of the following code fragments: a, int sum=0; for (int k n: k > 0; k /= 2) for (int i 0; ǐ < k; İ++) sum++; b.int sum 0; for (int i = 1; i < n; i *= 2) for (int j = 0; j < i; j++) sum++;

Answer 1

$\color{blue}\underline{a:}$

First for loop is running for log(n) times.
Inner for loop is running for k times. Where max value for k is n.
So, time complexity = O(nlog(n))

$\color{blue}\underline{b:}$

First for loop is running for log(n) times.
Inner for loop is running for i times. Where max value for i is n.
So, time complexity = O(nlog(n))

$\color{blue}\underline{c:}$

First for loop is running for log(n) times.
Inner for loop is running for n times.
So, time complexity = O(nlog(n))