Question

Analyze the running time of the following algorithms asymptotically. (a) Algorithm for-loop(n): P = 1 for i = 1 to 5n^2 do p = p times i return p (b) Algorithm for-loop(n): s = 0 for i = 1 to n do for j = I to n do s = s + i return s (c) Algorithm WhileLoop(n): x = 0; j = 2; while (j = n){x = x+ 1; j =j times 2;}

Answer 1

(a) It simply run 5*n² times . Hence, its time complexity is O(n ²)

(b) There are two nested for loops. for each outer contains variable i, inner loop will run n-i times.

hence it runs n + n-1 + n-2....1 = n*(n+1)/2 times.

Hence , its time complexity is  O(n ²)

(c) Here the value of j varies from

2,4,8....n

Hence it will run log₂ n -1 times. Hence, its time complexity is O(log₂ n) times