0 votes 0 votes closed as a duplicate of: TIME COMPLEXITY What is time complexity of fun()? int fun(int n) { int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count; } (A) O(n^2) (B) O(nLogn) (C) O(n) (D) O(nLognLogn) Algorithms algorithms time-complexity geeksforgeeks-test-series + – Sumit Singh Chauhan asked Aug 18, 2018 • closed Jan 10 by Hira Thakur Sumit Singh Chauhan 3.5k views comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Shubhgupta commented Aug 18, 2018 i edited by Shubhgupta Aug 18, 2018 reply Follow Share simply unroll the dependency.. when i=n ,j will run n times i=n/2, j will run n/2 times i=n/4, j=n/4 i=n/8,j=n/8 ----------------------- Total Complexity = n + n/2 + n/4 + n/8 .............. = n(1 + 1/2 +1/4 + 1/8............ logn times) = O(n) (1 + 1/2 +1/4 + 1/8............ logn times) this value will be nearly 1. 0 votes 0 votes Sumit Singh Chauhan commented Aug 18, 2018 reply Follow Share what is the equation of log n. 0 votes 0 votes Rishav Kumar Singh commented Aug 18, 2018 i edited by Rishav Kumar Singh Aug 18, 2018 reply Follow Share i think you got it 3 votes 3 votes Please log in or register to add a comment.
1 votes 1 votes in this problem ...how many times for loop will execute: first time loop: n times second time : n/2 times similarly form series = n +n/2 +n/4 + .....+1 its decreasing GP series TC = O(n) Hence option C is correct Hradesh patel answered Aug 18, 2018 Hradesh patel comment Share Follow See all 0 reply Please log in or register to add a comment.