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