How is the time Complexity of this problem O(n log log n)?

Question

int A(int n){
    for(i = 1; i < n; i++)
        for(j = 1; j < i; j *= 2)
            for(k = j; k >= 1; k /= 2)
                if(n = 0) return 1;
                else{
                    for(z = 0; z < n; z++){
                    // do something
                    }
                }
}

 

How do find the complexity of this problem?

The answer is supposed to be O(n log log n), but it maybe wrong.

Comments

gmrishikumar when i=2, j will run 1 time but k will run 1 time but as per above table it will run zero time 

loglog2--->log1---->0 times check once

Also check this 

https://ide.geeksforgeeks.org/QiAYKUUqzE

---

@Hemanth_13 You are right. I wasn't exactly precise here. There will be a little difference because of the loop conditions. But this is an approximation.

---

@Arjun sir, although we know the answer but no one knows how to solve this problem exactly.

Any help is appreciated.

Answer 1

I am getting O(nloglogn) .

Since the k loop is running loglogn times. Everytime k loop is executed , the z loop runs n times. Hence O(nloglogn)

 

Comments

@Sweta Shaw

Can you explain with procedure ?? How k is running loglogn times ??

---

As explained by @gmrishikumar .

for i =	1	2	..	n
j will run	log 1 times	log 2 times	...	log n times
hence k will run	log log 1  times	log log 2 times	...	log log n times

---

@Sweta Shaw But how do you approximate the sum.

As I previously mentioned

The number of iterations of the 3 outer for loops would be, 
log log 1 + log log 2 + log log 3 + ... + log log n 

Total time taken should be n * (log log 1 + log log 2 + log log 3 + ... + log log n).

How do you approximate in such cases? Or how do you take their sum?