CODEWITHSUNDEEP
pythonalgorithmtime-complexitybig-o
Jesse
Jesse

Reputation: 33

Time complexity of O(log n) nested in another O(log n) loop

I'm a bit confused about the time complexity of the following algorithm. I know that inserting into a heap is O(log n) with base 2, but the while loop that it's nested insides seems to be O(log n) with base 3. Would the time complexity be O(log n with base 3) * O(log n with base 2)?

i = 1
while i < len(L):
    insert L[i] into heap
    i = i*3

Upvotes: 1

Views: 571

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

Since i increases exponentially, you will be inserting floor(log3(L)) elements into heap.

Assuming that an insertion is O(log(n)), where n is the number of elements already in the heap (not the array L), doing m insertions to an initially empty heap will have complexity O(log 1 + log 2 + log 3 + ... log (m - 1)) = O(log([m - 1]!) = O(log(m!)).

According to Stirling's Approximation, ln(n!) = n ln n - n + O(ln n).

Substituting in the number of insertions, and ignoring the overshadowed O(n) terms, we have:

T(L) = O(log([floor(log3(L))]!))
     = O([floor(log3(L))][log(floor(log3(L)))])  // apply Stirling
     = O([log3(L)][log(log3(L))])  // a number rounded down only differs
                                      from its value by less than 1
     = O(log L * log log L)        // base of log only contributes to a constant

Upvotes: 2

Related Questions