+ 2

What is the TIME COMPLEXITY of the code given below -

for (int i=1; i< 2*n ;i++) for (int j=1;j<n*n /2;j*=2) sum = sum +1;

13th Oct 2019, 5:31 PM
Aadarsh Gupta
Aadarsh Gupta - avatar
4 ответов
+ 3
The inner loop will run log(n^2) - 1 times for each value of i in the outer loop (which runs 2n times) therefore time complexity is T(n) = 2n x (logn^2 - 1) = 4nlogn - 2n T(n) = O(nlogn) The inner loop will run logn^2 - 1 times because it takes the values as 1, 2, 2^2, 2^3, .... 2^x Now, 2^x = n^2/2 x = log(n^2/2) x = log(n^2) - 1
13th Oct 2019, 11:12 PM
Infinity
Infinity - avatar
+ 3
It's O(n log n), but you can make it O(1) as Anton Böhler said.
13th Oct 2019, 7:36 PM
Diego
Diego - avatar
+ 1
why do you put 'data' & 'structure' into your tags? 😅 here is a code that does it faster System.out.println((2*n-1)*Math.max((int)Math.ceil(Math.log(n*n/2) / Math.log(2)), 0));
13th Oct 2019, 6:51 PM
Anton Böhler
Anton Böhler - avatar
+ 1
Because TIME COMPLEXITY also occur in data structure basic theory as Big oh , Omega and Theta notation There is a topic named Asymptotic Notations
13th Oct 2019, 6:57 PM
Aadarsh Gupta
Aadarsh Gupta - avatar