#include <cassert>
#include <iostream>

// Discovering a formula from a recurrence
//
// In the previous example, we considered:
//
//             /
//            (   1                 n = 1
//             )
//     T(n) = <
//             )
//            (   T(n - 1) + 1     n > 1
//             \
//
// and discovered:
//
//     T(n) = n.
//
// Now consider a slightly different recurrence:
//
//             /
//            (   1                 n = 1
//             )
//     T(n) = <
//             )
//            (   T(n - 1) + n     n > 1
//             \
//
// Author the function T(n), asserting that:
//
//     n >= 1.
//
// Then, in main(), write a loop that calculates:
//
//     T(1), T(2), T(3), ...
//
// until you can determine a formula for T(n).
//
// As before, begin by calculating values and looking
// for a pattern.

// Function declarations
int main();

unsigned int T(
    unsigned int const n
);

// Function definitions
int main() {
    // Your implementation here.

    return 0;
}


// unsigned int T( ... )
//
// @param n
//     A positive integer.
//
// @returns
//     The value defined recursively by:
//
//         T(1) = 1
//
//     and:
//
//         T(n) = T(n - 1) + n
//
//     for n > 1.

unsigned int T(
    unsigned int const n
) {
    assert( n >= 1 );

    // Your implementation here.

    return 1;
}














































// Hint
//
// Begin by printing:
//
//     T(1)
//     T(2)
//     T(3)
//     ...
//
// For example:
//
//     for ( unsigned int k{ 1 };
//           k <= 10;
//           ++k ) {
//         std::cout << "T(" << k << ") = "
//                   << T( k )
//                   << std::endl;
//     }
//
// What pattern do you observe?
//
// This time:
//
//     T(n) = T(n - 1) + n.
//
// Thus, the amount being added is not always 1.
//
// It changes as n changes.














































// Solution

/*
int main() {
    for ( unsigned int k{ 1 };
          k <= 10;
          ++k ) {
        std::cout << "T(" << k << ") = "
                  << T( k )
                  << std::endl;
    }

    return 0;
}

unsigned int T(
    unsigned int const n
) {
    assert( n >= 1 );

    if ( n == 1 ) {
        return 1;
    } else {
        return T( n - 1 ) + n;
    }
}
*/














































// What is the pattern?
//
// Running the program produces:
//
//     T(1)  =  1
//     T(2)  =  3
//     T(3)  =  6
//     T(4)  = 10
//     T(5)  = 15
//     T(6)  = 21
//     T(7)  = 28
//     T(8)  = 36
//     T(9)  = 45
//     T(10) = 55
//
// This pattern may not be as immediately obvious as
// the previous one.
//
// Let us expand some of the calculations:
//
//     T(1) = 1
//
//     T(2) = T(1) + 2
//          = 1 + 2
//          = 3
//
//     T(3) = T(2) + 3
//          = 1 + 2 + 3
//          = 6
//
//     T(4) = T(3) + 4
//          = 1 + 2 + 3 + 4
//          = 10
//
//     T(5) = T(4) + 5
//          = 1 + 2 + 3 + 4 + 5
//          = 15
//
// The recurrence is therefore calculating:
//
//     T(n) = 1 + 2 + 3 + ... + (n - 1) + n.
//
//
//
// Do you recognize this sum?
//
// In secondary school, you may have learned:
//
//     1 + 2 + 3 + ... + n
//
//         n(n + 1)
//       = ----------.
//             2
//
// Therefore:
//
//            n(n + 1)
//     T(n) = ----------.
//                2
//
//
//
// We can also derive this directly from the
// recurrence.
//
// Start with:
//
//     T(n) = T(n - 1) + n.
//
// Apply the definition to T(n - 1):
//
//     T(n)
//       = T(n - 2) + (n - 1) + n.
//
// Again:
//
//     T(n)
//       = T(n - 3)
//         + (n - 2)
//         + (n - 1)
//         + n.
//
// Continuing:
//
//     T(n)
//       = T(1) + 2 + 3 + ... + (n - 1) + n.
//
// Since:
//
//     T(1) = 1,
//
// we obtain:
//
//     T(n)
//       = 1 + 2 + 3 + ... + (n - 1) + n
//
//       = n(n + 1)/2.
//
//
//
// How quickly does this grow?
//
// We now have an exact formula:
//
//            n(n + 1)
//     T(n) = ----------
//                2
//
//            n^2 + n
//          = --------.
//                2
//
// For large n, the n^2 term dominates.
//
// Therefore:
//
//     T(n) = Theta(n^2).
//
//
//
// Compare this with the previous recurrence.
//
// Previously:
//
//     T(n) = T(n - 1) + 1
//
// gave:
//
//     T(n) = n
//
// and therefore:
//
//     Theta(n).
//
//
// Now:
//
//     T(n) = T(n - 1) + n
//
// gives:
//
//     T(n) = n(n + 1)/2
//
// and therefore:
//
//     Theta(n^2).
//
//
// The difference is important.
//
// In both cases, the problem becomes smaller by one:
//
//     n -> n - 1 -> n - 2 -> ... -> 1.
//
// However, the amount of work performed at each step
// is different.
//
// First recurrence:
//
//     n       work: 1
//     n - 1   work: 1
//     n - 2   work: 1
//       ...          ...
//     1       work: 1
//
// so the total resembles:
//
//     1 + 1 + 1 + ... + 1.
//
//
// Second recurrence:
//
//     n       work: n
//     n - 1   work: n - 1
//     n - 2   work: n - 2
//       ...          ...
//     1       work: 1
//
// so the total resembles:
//
//     n + (n - 1) + (n - 2) + ... + 1.
//
//
//
// A picture of the work
//
// The first recurrence:
//
//     *
//     *
//     *
//     *
//     *
//     *
//     *
//
// contains approximately n units of work.
//
//
// The second recurrence:
//
//     *******
//     ******
//     *****
//     ****
//     ***
//     **
//     *
//
// contains a triangular amount of work.
//
// This is why:
//
//     1 + 2 + 3 + ... + n
//
// is sometimes called a triangular number.
//
//
//
// Where does this occur in an algorithm?
//
// Recall selection sort.
//
// Suppose there are n entries:
//
//     [          unsorted          ]
//
// We search through the unsorted portion to find an
// entry that belongs in its final position.
//
// We then have a smaller problem:
//
//     [       unsorted       | x ]
//
// Then:
//
//     [    unsorted    | x   x ]
//
// Then:
//
//     [ unsorted | x   x   x ]
//
// and so on.
//
// The amount of searching decreases on each pass.
//
// Very roughly, the work has the form:
//
//     n
//     + (n - 1)
//     + (n - 2)
//     + ...
//     + 2
//     + 1.
//
// Thus, a recurrence such as:
//
//     T(n) = T(n - 1) + n
//
// captures the essential growth of selection sort.
//
// Solving the recurrence gives:
//
//     T(n) = n(n + 1)/2
//
// and therefore:
//
//     T(n) = Theta(n^2).
//
//
//
// Counting comparisons exactly
//
// There is one small but important distinction.
//
// If we search n entries to find the maximum, we do
// not actually require n comparisons.
//
// For example, to find the larger of:
//
//     4   7
//
// requires one comparison.
//
// To find the largest of:
//
//     4   7   2
//
// requires two comparisons.
//
// In general, finding the maximum of n entries
// requires:
//
//     n - 1
//
// comparisons.
//
// Therefore, if T(n) counts the ACTUAL comparisons
// performed by selection sort, a more precise
// recurrence would be:
//
//             /
//            (   0                       n = 1
//             )
//     T(n) = <
//             )
//            (   T(n - 1) + (n - 1)     n > 1.
//             \
//
// Expanding this gives:
//
//     T(n)
//       = (n - 1) + (n - 2) + ... + 2 + 1
//
//       = n(n - 1)/2.
//
//
//
// Thus, we have two related formulas:
//
//     1 + 2 + ... + n
//
//         = n(n + 1)/2
//
//
// and:
//
//     1 + 2 + ... + (n - 1)
//
//         = n(n - 1)/2.
//
//
//
// Which one should we use?
//
// It depends on what T(n) represents.
//
// If we are describing the work only approximately,
// we may write:
//
//     T(n) = T(n - 1) + n.
//
// This captures the important behavior and leads to:
//
//     Theta(n^2).
//
//
// If we are counting the exact number of comparisons
// performed by selection sort, we should write:
//
//     T(n) = T(n - 1) + (n - 1),
//
// giving:
//
//     T(n) = n(n - 1)/2.
//
// Both analyses lead to the same asymptotic result:
//
//     Theta(n^2).
//
//
//
// This illustrates another important idea.
//
// When analyzing an algorithm, always ask:
//
//     What exactly is T(n) counting?
//
// It might count:
//
//     comparisons,
//
//     assignments,
//
//     swaps,
//
//     additions,
//
//     function calls,
//
// or some other representative operation.
//
// Different choices can give slightly different
// exact formulas.
//
// What matters for asymptotic analysis is how those
// formulas grow as n becomes large.
//
//
//
// From the algorithm to the runtime
//
// For selection sort:
//
//     ALGORITHM
//
//         find the largest remaining entry
//
//         recursively sort n - 1 entries
//
//                  |
//                  v
//
//     RECURRENCE
//
//         T(n) = T(n - 1) + (n - 1)
//
//                  |
//                  v
//
//     FORMULA
//
//         T(n) = n(n - 1)/2
//
//                  |
//                  v
//
//     ASYMPTOTIC RUNTIME
//
//         Theta(n^2)
//
//
//
// Questions:
//
// 1. What values do you obtain for T(1) through
//    T(10)?
//
// 2. What familiar sequence do these values form?
//
// 3. What sum is represented by T(n)?
//
// 4. What is the formula for:
//
//        1 + 2 + 3 + ... + n?
//
// 5. Why does this formula contain an n^2 term?
//
// 6. Why is T(n) therefore Theta(n^2)?
//
// 7. How is this recurrence different from:
//
//        T(n) = T(n - 1) + 1?
//
// 8. If finding the maximum of n entries requires
//    n - 1 comparisons, what recurrence describes
//    the exact number of comparisons in selection
//    sort?
//
// 9. How many comparisons does selection sort
//    perform on an array containing n entries?
//
// 10. Why do:
//
//        n(n + 1)/2
//
//     and:
//
//        n(n - 1)/2
//
//     both have the same asymptotic growth?
//
//
//
// The important progression so far is:
//
//     T(n) = T(n - 1) + 1
//
//         |
//         v
//
//     T(n) = Theta(n)
//
//
//
//     T(n) = T(n - 1) + n
//
//         |
//         v
//
//     T(n) = Theta(n^2)
//
//
//
// In both cases, the recursive problem has size
// n - 1.
//
// What changed was the amount of work performed
// before or after the recursive call.
//
// That observation will become increasingly useful
// as we examine more interesting recurrences.