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

• 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.

• 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)``

• 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).

• @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)?

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