DERIVING TIME COMPLEXITY FUNCTIONS:

Example Algorithm #1:

    read n                    --
    sum = 0                    |
    i = 1                      |
    while (i <= n)        --   |
        sum = sum + i --   |   |         T(n) = 3n + 5
        i = i + 1     --  --   |
    print sum          |   |  --
                       2   |   | 
                           |   |
                n(2 + 1) + 1   |
                = 3n + 1       |
                               |
                    (3n + 1) + 4
                    = 3n + 5


Example Algorithm #2: 

    read n                                   --
    sum = 0                                   |
    i = 1                                     |
    while (i <= n)                       --   |
        j = 1                        --   |   |
        while (j <= n)           --   |   |   |      T(n) = 3n^2 + 4n + 5
            sum = sum +       --  |   |   |   |
               (i * (j + 1))   |  |   |   |   |
            j = j + 1         -- --   |   |   |
        i = i + 1              |  |  --  --   |
    print sum                  |  |   |   |  --
                               2  |   |   |   |
                                  |   |   |   |
                       n(2 + 1) + 1   |   |   |
                       = 3n + 1       |   |   |
                                      |   |   |
                           (3n + 1) + 2   |   |
                           = 3n + 3       |   |
                                          |   |
                        n((3n + 3) + 1) + 1   |
                        = 3n^2 + 4n + 1       |
                                              |
                            (3n^2 + 4n + 1) + 4
                            = 3n^2 + 4n + 5


Example Algorithm #3: Worst-Case Analysis

    read n                              --
    index = 1                            |
    max = MIN_INTEGER                    |
    i = 1                                |
    while (i <= n)                  --   |
        read value              --   |   |
        if (value > max)     --  |   |   |   T(n) = 6n + 6
            max = value  --   |  |   |   |
            index = i    --  --  |   |   |
        i = i + 1         |   | --  --   |
    print index, max      |   |  |   |  --
                          2   |  |   |   |
                              3  |   |   |
                                 5   |   |
                                     |   |
                          n(5 + 1) + 1   |
                          = 6n + 1       | 
                                         |
                                6n + 1 + 5 
                                = 6n + 6


Example Algorithm #3: More Complex Analysis, i.e., incorporates 
                       function for # times IF-condition evaluates 
                       to TRUE.

    read n                               --
    index = 1                             |
    max = MIN_INTEGER                     |
    i = 1                                 |
    while (i <= n)               --  --   |
        read value           --   |   |   |
        if (value > max)      |   |   |   |      T(n) = 4n + 2k + 1
            max = value  --   *   *   |   |
            index = i    --   *   *   |   |
        i = i + 1         |  --  --  --   |
    print index, max      |   |   |   |  --
                          2   |   |   |   |
                              3   |   |   |
                                  |   |   |
                       n(3 + 1) + 1   |   |
                       = 4n + 1       |   |
                                      |   |
                         4n + 1 + 2k (*)  |
                                          |
                          (4n + 1 + 2k) + 5
                          = 4n + 2k + 6

  (*) = Note that the statements associated with the If are only
         executed k times, where k is the length of the longest
         increasing subsequence in the input list (for example,
         in the sequence of numbers {1, 3, 2, 7, 2, 4, 1, 9, 5}.
         the longest increasing subsequence is {1, 3, 7, 9} such
         that k = 4). In the worst case, i.e., a sequence in
         sorted order, k = n and we have the results of the first
         analysis. However, in the best case, i.e., a sequence in
         reverse sorted order, k = 1 and we have the best-case
         running time of T(n) = 4n + 8.