CODEWITHSUNDEEP
algorithmbig-o
user3041349
user3041349

Reputation: 43

What time complexity is this nested loop with multiplication?

educative.io think that the below code has complexity log2(n!) because var increases for each value of n.

However, my associate and I think that because var is always < n there is no way that it could be log2(n!) because it would never take more time than if the while loop just ran off n. The time complexity if n were used in the while predicate is n*log2(n).

public static void main(String[] args) {
    int n = 10;   

    for (int var = 0; var < n; var++) {   
      int j = 1;  
      while(j < var) { 
        j *= 2;  
      }
    }
}

Upvotes: 2

Views: 186

Answers (2)

Ehsan Gerayli
Ehsan Gerayli

Reputation: 594

You should consider this statement and you both are right:

O(n*lg(n))=O(lg(n!))

Upvotes: -1

John Kugelman
John Kugelman

Reputation: 361615

You're both right. First, the case for why it's O(log n!):

  • If you add up the cost of each individual iteration, the overall runtime is O(log 1 + log 2 + ... + log n).

  • By the product rule of logarithms, log a + log b = log a×b.

  • Therefore, O(log 1 + log 2 + ... + log n) = O(log 1×2×...×n) = O(log n!).

Once that's established, it can be shown that O(log n!) = O(n log n). They are actually the same complexity class.

Upvotes: 3

Related Questions