exam-review-algorithm-analysis.c

// 1. Determine if two numbers, x and y, are relatively prime. Compute for T(n) of your solution. 
// Two integers are relatively prime if they share no common positive factors (divisors) except 1.

// 2. Compute for T(n):

for (int i = 1; i <= n; i++) {
  a = x - y + 7 * b;
  for (int j = 1; j <= n; j++) {
    x = a + b;
    for (int k = j; k <= n; k++) {
      cout << "hi" << endl; 
    }
  }
}

// 3. Compute for T(n):

for (int i = 1; i <= n; i++) 
  for (int j = i; j <= n; j++)
    for (int k = j; k <= n; k++)
      cout << "hey!" << endl;

// 4. Simplify the following recurrence relation: T(n) = 2T(n / 2) + n

// For reference - common recurrence relations and their solutions:
// http://papl.cs.brown.edu/2016/predicting-growth.html#%28part._solving-recurrences%29