Question

What does a run-time analysis usually countS pts a. The number of arithmetic and other operations required fot the b. The number of megabytes required for the program to run c. The number of seconds required for the program to run. d. The number of seconds plus the number of megabytes Total 100 points, 30 ins and other operations required for the program to rn 2. What do we call an input that results in the longest execution timet a. Best-case input. b. Average-case input c. Worst-case input. d. None of the above. 3. For the following big-Oh notation in terms of n, which runs the fastest. cs p a. n b. (log(n))2 c. n d. log(n) 4. What is the Big Oh of the following terms: <20 pts> a. 5n2 +2 is b. n+ 1000 log(n)+ 7 is: c. 5n3 +10n2-n-8 is: d. 3n2 + 2"is: Analyze the running time of each piece of the following code, give best big in terms of n. <10 pts> 5. for ( i = n; ǐ > 0; İ--) Answer:_ b. sum0; for(k 0; k< ji k++) sum++; Answer:

Answer 1

1) d. because during the runtime of the program we are actually looking at what is that actual running time and the space required by the program.

2) c. because worst case is the input during which will take the most time average will talk about the average running time and best will tell the least running time.

3) d. log(n) will be slowest after which log(n)^2 and then n and then n^2

4) a.

d. because during the runtime of the program we are actually looking at what is that actual running time and the space required by the program. c. because worst case is the input during which will take the most time average will talk about the average running time and best will tell the least running time. d. log(n) will be slowest after which log(n)^2 and then n and then n^2 a. O(n^2) b. O(n) c. O(n^3) d. O(2^n) a. For i = n, j will run for n - 1, i = n - 1 j will run for n - 2 and so on till 1. So the total number of iterations will be 1 + 2 + 3 + 4 +...+ n-1, which sum will be (n-1)*(n)/2 = O(n^2) . b. Although i is going from 1 to n^2 but still only n iterations are working in i, n iterations for j and variable number of instruction ranging from 0 to n for k. So the total number of iterations will sum to O(n^3)

b. O(n)

c. $O(n^3)$

d. $O(2^n)$

5) a. For i = n, j will run for n-1, i=n-1 j will run for n-2 and so on till 1. So the total number of iterations will be 1+2+3+4+...+n-1, which sum will be (n-1)*(n)/2 = $O(n^2)$ .

b. Although i is going from 1 to n^2 but still only n iterations are working in i, n iterations for j and variable number of instruction ranging from 0 to n for k. So the total number of iterations will sum to $O(n^3)$ .