Time Complexity and recursion Practice

Analyze these Algorithms - Run each of the 3 loops below.

Note: Use the following to help time the following questions

 long startTime = System.nanoTime() ; 

 //call to method 

 long endTime = System.nanoTime() ; 

 long totalTime = endTime - startTime; 

 System.out.println(totalTime); 

Loop 1:

public static int run(int n) { 

 int sum = 0; 

 for (int i=0 ; i < n ; i++) 

 for (int j=0 ; j < n ; j++) 

 sum++; 

 return sum; 

} 

A) What is the Big-Oh running time?

B) Run the code with several values of N.

C) Create a table with at least 5 different values of N with the run time in milliseconds.

Loop 2:

public static int run(int n) { 

 int sum = 0; 

 for (int i=0 ; i < n ; i++) 

 for (int j=0 ; j < n * n ; j++) 

 sum++; 

 return sum; 

 } 

A) What is the Big-Oh running time?

B) Run the code with several values of N.

C) Create a table with at least 5 different values of N with the run time in milliseconds.

Loop 3:

Create your own loop! (write the code here)

A) What is the Big-Oh running time ?

B) Run the code with several values of N.

C) Create a table with at least 5 different values of N with the run time in milliseconds.

Part 2: 5pts

Base Conversion

Write a program that uses recursion to convert a base 10 number into a base b number, where b < 10. If the number to be converted is n, then the algorithm to convert n to base b is:

1) Divide n by b. Store the quotient and the remainder.

2) The remainder is the rightmost digit of the final answer.

3) The quotient is now the new number n that you will recursively convert to base b.

4) Repeat step a by calling your recursive method with the quotient and the original base b.

5) Stop when n / b = 0. The remainder at this point will be the first digit of the final answer.

For example, to convert 30 into a base 4 number:

Quotient Remainder

30/4 7 2

7/4 1 3

1/4 0 1

The answer is the remainder column read bottom to top, so 30 (base 10) = 132 (base 4).

A skeleton of the recursive method is given below.

public static String convert(int number, int base)

{

int quotient =

int remainder =

if( )

return( + );

else

return( ) + );

}

Sample Output:

Enter a number to convert: 48

Enter a base to convert to: 8

48 converted into base 8 is 60.

Enter a number to convert: 157

Enter a base to convert to: 2

157 converted into base 2 is 10011101.

Part 3: 10pts

The Ackermann Function

The Ackermann function is a function created by Wilhelm Ackermann in the late 1920s. For non-negative integers m and n, the Ackermann function is defined as

A(m,n)= n+1 if m=0

A(m,n) = A(m-1,1) if m>0 and n=0

A(m,n)= A(m-1, A(m,n-1)) if m>0 and n>0

Write a method to recursively computer the Ackermann function. Note that the Ackermann function grows extremely quickly for even small values of m and n. Test your method with the following values but be aware that if m is greater than 3 and n is greater than 1, it will take a very long time to compute.

	n
m	0	1	2	3	4	5	6	7	8	9	10
0	1	2	3	4	5	6	7	8	9	10	11
1	2	3	4	5	6	7	8	9	10	11	12
2	3	5	7	9	11	13	15	17	19	21	23
3	5	13	29	61	125	253	509	1021	2045	4093	8189

Part 4: 5pts

Write a recursive method called writeNums that takes an integer n as a parameter and prints to the console the first n integers starting with 1 in sequential order, separated by commas. For example, consider the following calls:

writeNums(5); // would produce 1, 2, 3, 4, 5

writeNums(12); //would produce 1, 2, 3, 4, 5, 6, 7, 8, 8, 10, 11, 12