What time complexity is this nested loop with multiplication?

Question

educative.io think that the below code has complexity log₂(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*log₂(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;  
      }
    }
}

Answer 1

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.

Answer 2

You should consider this statement and you both are right:

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