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(2^{n-1}). This can be shown by induction:

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

Assume for `n=k`

, C(k) = 2^{k-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) = 2^{n-1}.