Question

1. For each pseudo-code below derive the simplified asymptotic running time in Q(?) notation.

(1)

for 1 <-- .. n do

j <- 2

   while j <= n do j <-- j*j

(2)

for i <-- 1 .. n do

j <-- 1

    while j*j <= i do j <-- j + 1

Answer 1

(1)

for 1 <-- .. n do

j <- 2

   while j <= n do j <-- j*j

Answer:O(n*√n)

Explanation:

The Outer loop runs for N time , while the inner loop runs for √n time. The Total time taken is n*√n => n^3/2

=> O(n*√n)

(2)

for i <-- 1 .. n do

j <-- 1

    while j*j <= i do j <-- j + 1

Answer:O(n*√n)

Explanation:

The Outer loop runs for N time , while the inner loop runs for √n time. The Total time taken is n*√n => n^3/2

=> O(n*√n)

Thanks, PLEASE COMMENT if there is any concern.