This is a problem that's introduced in Introduction to Algorithms on the maximum subarray problem.
Very briefly, the main problem is something like this: You're given data on the price of a stock over $n$ days, and you'd like to find a pair of days that would maximize your profit (one day = buy, the other = sell).
The book begins by considering the brute-force approach, which is to consider all possible $(buy, sell)$ day combinations. The book claims that for $n$ days, there are ${n \choose 2}$ ways to pick such days.
This doesn't seem right to me, and I'd like to get some clarification. Here is how I've worked out the computations so far:
Consider the array $[day1, day2, day3, ..., dayn]$. Obviously, we can't ever buy the stock on $dayn$ because then we can't sell it. So I believe there are only $n-1$ options for the purchase day.
As for the second day (sell), let's consider this. You could pick the following for the purchase date and have the corresponding number of sell options:
- $day1$: $n-1$ options (all days except $day1$ itself)
OR
- $day2$: $n-2$ options (all days except $day1$ and $day2$
OR
- $day3$: $n-3$ options (all days except $day1$, $day2$, and $day3$)
OR
...
OR
- $day(n-1)$: $1$ option (namely, the $n$th day)
So this is a summation:
$1 + 2 + 3 + ... + (n-1)$
And that's $\frac{(n-1)(n)}{2}$.
So that's how many options we have for the $sell$ day. Giving us a total asymptotic complexity for the number of choices of:
$(n-1) \times \frac{(n-1)(n)}{2} = O(n^3) $ in Big-O notation
Again, the book claims it's ${n \choose 2}$ and that this is really $O(n^2)$. Where am I going wrong in my understanding?