+ 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;
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
+ 3
It's O(n log n), but you can make it O(1) as Anton Böhler said.
+ 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));
+ 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