Consider the following nested loop construct. Categorize its efficiency in terms

Question

 Consider the following nested loop construct. Categorize its efficiency in terms of the variable n using âbig-o" notation. Suppose the statements represented by the ellipsis (. . . ) require four main memory accesses (each requiring one microsecond) and two disk file accesses (each requiring one millisecond). Express in milliseconds the amount of time this construct would require to execute if n were 1000

x=1; do { y = n; while (y < 0) { y--; } x *= 2; } while ( x < n*n);
x=1; do { y = n; while (y < 0) { y--; } x *= 2; } while ( x < n*n);

Explanation / Answer

actually your code is wrong, it should have been while( y > 0 )

Anyway, I am giving the solution for y>0 not y<0 because y<0 doesnot have any sense..

you see, do-while loop runs for O(logn) times..now comes the question why so.. Here you see x*=2, so value of x will be = 1,2,4,8,16, .. such that x<n*n..i.e x= 2^0,2^1,2^2,2^3,2^4 ...2^h..such that x<n*n ..

so here, the do-while loop will run for "h" number of times such that 2^h<n*n i.e 2^h<n^2,

now take logarithm with base 2 on both side, we get, h<2*logn (with base 2)

so time complexity for do-while loop is O(2logn) which is actually written as O(logn)..

now you see inner while loop is running for n times for every value of x; i.e O(n) time complexity

so total time complexity for nested loop construct= O(nlogn)..

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---