Big-O notation

First code segment

1.  The outer loop performs n iterations.
    For each of those iterations, the loop in which methodA() is called 
    performs 2n iterations.
    Thus, methodA() is called n*(2n) = 2n^2 times.
    The corresponding big-O expression is O(n^2).

2.  For each of the 2n^2 iterations performed by the loop in which methodA()
    is called, the loop in which methodB() is called performs n + 1 iterations.
    Thus, methodB() is called 2n^2(n + 1)
                            = 2n^3 + 2n^2 times
    Because the fastest-growing term is the 2n^3 term, methodB() is called O(n^3) times.

3.  For each value i of the outer loop's variable, the loop in which methodC() is called 
    performs i iterations.
    Thus, the total number of times that methodC() is called is: 
        0 + 1 + 2 + ... + (n-2) + (n-1) = (n^2)/2 - n/2.
    Thus, methodC() is called O(n^2) times. 

4.  When the value of the outer loop variable i is even, methodD() is called. 
    When i is odd, methodD() is not called.
    Thus, for approximately n/2 values of i, methodD() is called,
    and therefore it is called O(n) times

Second code segment

a) The outer loop performs n - 1 repititions. Thus, the line that 
assigns x the value of a[i] is repeated (n - 1) = O(n) times.


b) For each of the n - 1 repetitions of the outer loop, the first 
nested loop performs 3 repetitions. Thus, the line sum *= a[i]
is repeated 3(n - 1) = 3n - 3 = O(n) times.


c) For each of the n - 1 repetitions of the outer loop, the second
nested loop (the while loop) performs i repetitions, where i
is the current value of the outer loop variable. Thus, the line 
result += a[j] is executed:

   1 time when i = 1
   2 times when i = 2
   3 times when i = 3
       ...
   n-1 times when i = n-1

and the total number of executions is the sum of the arithmetic
sequence 1 + 2 + 3 + ... + (n - 1) = O(n^2)