EECS2030 Test 5B

Programming question

Implement the Test5B class. A skeleton can be found here. The API can be found in the skeleton.

You have to put your Test5B class in the test5 package.
You have to use recursion.
The methods charAt, substring and length of the String class might be useful.

Other questions

Consider the following method.

/**
 * Returns 6n + 6, where n is the given integer.
 *
 * @param n an integer.
 * @pre. 0 <= n && n <= 100.
 * @return 6n + 6.
 */
public static int recursive(int n) 
{
   if (n == 100)
   {
      return 606;
   }
   else if (n == 99)
   {
      return 600;
   }
   else
   {
      return recursive(n + 2) - 12;
   }
}

Question 1

Prove the above method correct.

Question 2

Prove that the above method terminates.

Question 3

Give the recurrence relation of the above method. You do not have solve the recurrence relation.

Question 4

Let f : ℕ → ℕ be defined by f(n) = 8n + 3 log(n) + 4. Then f ∈ O().

Question 5

Prove your answer to Question 4.

We pick M = and F = . Let n ≥ . Then