CS2230 Data Structures and Algorithms Lab
Algorithm Analysis
Completing this lab will prepare you for additional algorithm analysis questions in HW4.
Revision
1. Revise your answers to Prelab from what you learned in lab this week.
the running time for input of size N. For each problem, please provide
i. summation
ii. explanation of how the code relates to the summation
iii. your f(N)
2. R(N) is the running time of superGreat(N)
static void superGreat(int n){
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n; j += 2) {
System.out.println("great");
}
} }
3. R(N) is the running time of frozen when called on an array of length N. Since this is recursive code, your (ii) should include a diagram of the recursion tree.
static int frozen(int[] arr) {
return frozen_helper(arr, arr.length);
}
static int frozen_helper(int[] arr, int n) { if (n <= 1) {
return 1; }
int s = 1;
for (int i=0; i