CODEWITHSUNDEEP
time-complexitycomplexity-theory
Neel Alex
Neel Alex

Reputation: 733

Nested loops with time complexity log(log n)

Can there be an algorithm with two loops (nested) such that the overall time complexity is O(log(log n))

This arised after solving the following :

for(i=N; i>0; i=i/2){
  for(j=0; j<i; j++){
    print "hello world"
  }
}

The above code has time complexity of N. (Using concept of Geometric Progression). Can there exists similar loop with time complexity O(log(log n)) ?

Upvotes: 1

Views: 791

Answers (1)

kaya3
kaya3

Reputation: 51063

For a loop to iterate O(log log n) times, where the loop index variable counts up to n, then the index variable has to grow like the inverse function of log log k where k is the number of iterations; i.e. it has to grow like 2^2^k, or some other base than 2.

One way to achieve this is by starting at 2 and repeatedly squaring until you reach n - if the index variable is (((2^2)^2)...^2) with k squarings, then this equals 2^2^k as required:

for(int i = 2; i < n; i = i*i) {
    //...
}

This loop iterates O(log log n) times, as required. If you absolutely must do it with nested loops, we can trivially add an extra loop which iterates O(1) times, leaving the total number of iterations asymptotically the same:

for(int i = 2; i < n; i = i*i) {
    for(int j = 0; j < 10; j++) {
        // ...
    }
}

Upvotes: 4

Related Questions