3 votes 3 votes //Consider the program void function(int n) { int i,j,count=0; for(i=n/2;i<=n;i++) for(j=1;j<=n;j=j*2) count++; } The complexity of the program is $O(\log n)$ $O(n^2)$ $O(n^2 \log n)$ $O(n \log n)$ Programming in C isrodec2017 + – gatecse asked Dec 17, 2017 • recategorized Feb 11, 2018 by srestha gatecse 3.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes Both the loops will run independent of each other. The outer loop will run for n/2 times. The inner loop will run for (log n) times. So, time complexity will be O (n log n). Option D. Anmol_Binani answered Dec 20, 2017 • selected Feb 12, 2018 by Prashant. Anmol_Binani comment Share Follow See 1 comment See all 1 1 comment reply Soumya29 commented Apr 10, 2018 reply Follow Share Outer loop will run from n/2 to n i.e n/2 times and for each value of i inner loop will run log n times. $\frac{n}{2}$ * logn = O(nlogn) 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes n/2 * logn = o(nlogn) REGGIE S answered Dec 19, 2017 REGGIE S comment Share Follow See all 0 reply Please log in or register to add a comment.