Lab W1D2
Question 1. Comparing Algorithms (a) In this lab, for all three algorithms you will (b) write the pseudo code. (Must follow the notations and conventions used in today’s Lecture) (c) determine the worst case time complexity.
Compare your empirical results from W1D1 with W1D2. Are they consistent? What did you learn from W1D1 and W1D2?
Problem statement Find the largest distance between any two even integers in an integer array.
Algorithm 1. Create a new array consisting of even numbers only. Then use nested loops to solve the problem using the newly created array of even numbers only.
Algorithm 2. Use a nested loop to solve the problem without creating an extra array.
Algorithm 3. Use one loop. Find max and min of even integers. Compute max – min.
Question 2. Consider the following functions to determine the relationships that exist among the complexity classes they belong.
10, 1, n^3, n^1/3, log(log n), n^2, n^1/2, logn, log n^n, n^k(k > 3), n^1/k (k > 3), nlogn, ln n, 2^n, 3^n, n^n, n^1/2 logn, n^1/3 logn, n!.