edited by
8,489 views
0 votes
0 votes

An algorithm has two phases. The first phase, initialization, takes time O(n2 log n). The second phase, which is the main computation, takes time O(n3). What is the most accurate description of the complexity of the overall algorithm?

  1. O(n2 log n)
  2. O(n3)
  3. O(n3 log n)
  4. O(n3 + log n)

Im getting option 2 , is it correct ?

edited by

1 Answer

6 votes
6 votes

You can write the complexity as O(n3 + n2 Log n), but as the first term dominates the other (grows faster), just O(n3).

O(n3 + n2 Log n) = O(n3 [1 + Log n/n]) 

As n→∞, log n/n → 0.

= O(n[1+0]) = O(n3)

Related questions

0 votes
0 votes
0 answers
1
Dulqar asked Jan 24, 2017
4,943 views
if T(n) = n2 √ n thenT(n) = O(n2)T(n) = O(n2 log n)T(n) = O(n3)None of the aboveIm getting option 2 is it correct ?
0 votes
0 votes
1 answer
4