Reason why the best algorithm has to be Θ(n^2)


  • 3
    E

    Suppose the best algorithm has time complexity of T(n) when there are n layers. Then let's think about what T(n+1) would be for such a best algorithm. For us to find the minimum sum of n+1 layers, we have to check every possible item on the last layer. Since there are n+1 elements on the last layer, we have

    T(n+1) = T(n) + (n+1)  with T(1)=1
    ==> T(n) = 1 + 2 + ... + (n+1) = Θ(n^2)
    

    Why do we have to check all items on layer n+1? Think of the following example:

    Suppose we have 5 layers now and the sum of all minimum sum path to the elements on layer 5 are as follows:

    1    3    6    9    90
    

    Which of the above 5 elements could be in the minimum sum path if there is one more layer? The answer is any one. For example if layer 6 has the following numbers:

    100 100 100 100 100 1
    

    In this case, the minimum sum path is 90+1.

    ========================================

    Something kind of irrelevant:

    One other detail that might be interesting to some of you is how many possible paths there are. The answer is C(n) = O(2n-1). This can be shown by induction:

    n=1 ==> C(1) = 1
    

    Assume for n=k, C(k) = 2k-1, then for n=k+1, there are k elements on the last but one layer, for every element on that layer, it has two possible paths to the k+1 layer. Therefore

    C(k+1) = C(k)*2 = 2^((k-1)+1)
    

    Thus, C(n) = 2n-1.


  • 0

    Sounds like you're really proving Ω(n2), not so much O(n2).

    And you forgot the ^2 here:

    ==> T(n) >= 1 + 2 + ... + (n+1) = O(n)

  • 0
    E

    Yes, I was indeed trying to say the best algorithm has a n^2 time complexity, which is: the best possible algorithm is of Θ(n^2).


  • 0

    @ElementNotFoundException

    T(n+1) = T(n) + (n+1) with T(1)=1
    ==> T(n) = 1 + 2 + ... + (n+1) = Θ(n^2)

    Did you mean T(n) = 1 + 2 + ... + n = Θ(n^2)?


Log in to reply
 

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