Question

4. Big-Oh and Rune time Analysis: describe the worst case running time of the following pseudocode functions in Big-Oh notation in terms of the variable n. howing your work is not required (although showing work may allow some partial t in the case your answer is wrong-don't spend a lot of time showing your work.). You MUST choose your answer from the following (not given in any particular order), each of which could be re-used (could be the answer for more than one of I -IV.): 0(n2), 0(n3 log n), On log n), 0(n), O(n2 log n), О(ns), O(2n), О(a3), O(log n), o(I), o(u), O(a) I. void silly(int n) t Runtime for (int j 0; j < i; ++j) { System.out.printin("jj): for (int k 0: k<n 3i ++k) System.out.println("k- k); " + II. void silly(int n, int x, int y if (x < y) for (int k0: k<n ni +k) ( = " + k); system.out.print1n("k else + i); System . out .printin ("i-" III. void silly(int n) system.out.printin ("n)i silly (n-1)i if (n 0) return; IV. void silly(int n) t if (n <s 0) return; system.out.printin("nn) silly(n/2)

Answer 1

$\small \color{blue}Answer:\;\;$

1)  O(n^2)
2)  O(n^3)
3)  O(n)
4)  O(log n)

Answer 2

1. Describe the worst case running time(O(T(n))) of the following pseudo code functions. I. void MyFunction(int n) { for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) {cout<<(”j = ” + j);} for (int k = 0; k < n * 3; ++k) {cout<<(”k = ” + k);} } }