2.3

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search


This problem does appear to break down into a series of nested summations:

In the last summation, the formula is independent of the iterator, which translates into adding the value 1, times:

Now the third summation goes from to the formula on closer examination reveals that

is which is equal to

Since

So the summation boils down to

The formula in the second summation is independent of the iterator, which translates to adding , times.

which is



Time Complexity = O



Back to Chapter 2