What time complexity is this nested loop with multiplication?

user_3041349 0
Viewed 142

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;  
      }
    }
}
big-o algorithm
2 Answers

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.

user_685870

You should consider this statement and you both are right:

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