1 votes 1 votes Algorithms time-complexity programming-in-c asymptotic-notation test-series + – Rishabh Gupta 2 asked Aug 31, 2017 retagged Jul 13, 2022 by makhdoom ghaya Rishabh Gupta 2 1.3k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply joshi_nitish commented Aug 31, 2017 reply Follow Share it will be n + n/2 + n/3 + n/4 + n/5........n/n n(1 + 1/2 + 1/3 + 1/4.....1/n) = n*O(logn) = O(nlogn) 0 votes 0 votes Kiyoshi commented Jul 14, 2022 reply Follow Share $\sum_{i=1}^{n} \sum_{j=1}^{floor(n/i)}1$ $=\sum_{i=1}^{n} floor(n/i)-1+1$ $=\Theta{(nlogn)}$ 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes So, option A. Pinaki Dash answered Aug 31, 2017 selected Sep 1, 2017 by Rishabh Gupta 2 Pinaki Dash comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments BHAVESH d shah commented Sep 1, 2017 reply Follow Share Can we take j= n-1,n-2,n-3,n-4....n-n instead of j= n/1..n/2..n/n?? @Pinaki Dash 0 votes 0 votes Pinaki Dash commented Sep 1, 2017 reply Follow Share The no. of times 2nd 'for loop' runs is determined by the value of 'm' as j runs from 1 to m. And the value of m changes for each iteration of 1st 'for loop' because of m=n/i as i changes in each iteration of the 1st loop. That's why we write it as loop runs for n/1+n/2+n/3.... times Had it been like 'm=n-i' in place of 'm=n/i', then we would have written that the loop runs for (n-1)+(n-2)+(n-3)+....+(n-n) times. 1 votes 1 votes BHAVESH d shah commented Sep 1, 2017 reply Follow Share thanks 0 votes 0 votes Please log in or register to add a comment.