Question

1. Fill in the blanks by selecting the statements that can be true based on the statement in the first column.

	g(n) grows slower than f(n)	g(n) grows the same rate as f(n)	g(n) grows faster than f(n)
f(n)=O(g(n))
f(n)=o(g(n))
f(n)=Ω(g(n))
f(n)=ω(g(n))
f(n)=θ(g(n))

2. Group the following functions f1, f2, …, f10 into different groups, so that functions within the same group grow at the same asymptotic rate. Also list groups in increasing asymptotic growth rate order. Note logn has base 10 and lgn has base 2.

f1	1 + 2 + 3 + … + (n-1) + n
f2	nlogn
f3	(lgn)*( lgn)
f4	1 + 2 + 4 + 8 + … + 2m (n=2m)
f5	2lgn + 100
f6	64n + 32
f7	2(2n)
f8	10logn + 3
f9	2n
f10	log(n!)

3. Provide best-case and worst-case running time and space complexity analysis in Big-Oh notation for sort method.

	Big-O Notation	Brief Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity

// assume input array has at least 2 elements void sort(int[] arr) {        int n = arr.length;        boolean isOrdered = true;        for (int i=0; i<n-1; i++) {               if (arr[i] > arr[i+1]) {                      isOrdered = false;                      break;               }        }               if (isOrdered) return;               for (int i = 0; i < n - 1; i++) {               for (int j = 0; j < n - i - 1; j++) {                      if (arr[j] > arr[j + 1]) {                            int temp = arr[j];                            arr[j] = arr[j + 1];                            arr[j + 1] = temp;                      }               }        } }

4. Provide best-case and worst-case running time and space complexity analysis in Big-Oh notation for the second method.

	Big-O Notation	Brief Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity

public static void genCode(int n, List<Integer> list, Random random) {        int m = random.nextInt(100);        if (m != 50 ) {         if (n == 0) {              return;        } else {               list.add(m);              genCode(n-1, list, random);        }        } } public static void genCode(int n) {     List<Integer> list = new LinkedList<Integer>();     Random random = new Random();     genCode(n, list, random); }

Answer 1

Q1 solution

	Gn grows slower than fn	gn grows same as fn	gn grows faster than fn
F(n)=O(g(n))	False	true	true
F(n)=o(g(n))	False	false	true
F(n)=omega(g(n))	True	true	false
F(n)=Omegaw(g(n))	True	false	false
F(n)=theta(g(n))	False	true	false

Q2 solution

F_{​​​​​​8}>f5>f3>f9>f7>f10>f2>f1>f4

F8and f5 in one class

F3

F9,f7

F10,f2

F1

F4

Q4 solution

	Big oh	brief explanation
Best case Running time	constant	when m=50 on first call of function
Worst case Running time	n	recursive call n to 1 with m!=50 in all call.
Best case space complexity	constant	no additional space as returned on first call
Worst case space complexity	constant	O(n) n activation records for each recursive call

​​​

Q3 solution

	big oh	Brief explanation
Best case Running time	n	sorted list case
Worst case Running time	n​​​​​​2	0ne element not in order
Best case space	constant	no additional space required
Worst case space	constant	no additional space required