What is the TIME COMPLEXITY of the code given below -

Question

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

Answer 1

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

Answer 2

It's O(n log n), but you can make it O(1) as Anton Böhler said.

Answer 3

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));

Answer 4

Because TIME COMPLEXITY also occur in data structure basic theory as Big oh , Omega and Theta notation
There is a topic named Asymptotic Notations