Its core runs in O(n) time?


  • 1
    L

    In each value of count, there are nested iterations. To create left and right, it need the O(n/count), and the merge one is O(count). So, the complexity is still like O(n/count) * O(count) = O(n) ?

    I am not good at the algorithm. That's the reason I don't know how to calculate the complexity.


  • 0
    F

    I was only able to solve the problem in O(2N) with Hashtable. With O(NLogN) I got TLE on large input.


  • 0
    R

    Is O(n log(n)) because:

    Splits the list again and again at half:

    n + 2*n/2 + 4*n/4 + 8*n/8 ... until the result n/d is one.
    

    This means that runs n * log2n.

    Doesn't matter if in any recursion traverse one to get the middle and again to merge.

    n + n is still n

    This is the way works the complexity indicator.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.