211

--

# Final Test

My answers are in bold and underlined below

A program runs at 1 second per n. How much longer will a program that runs in n^3 take than a program that runs in n^2 if n = 25. (Hint: Answer = Larger n - Smaller n)

a. 16,900 seconds or 281 minutes

b.  15,000 seconds or 250 minutes: Correct Answer

25^3 - 25^2 = X

15625 - 625 = 15,000 seconds

c. 13,248 seconds or 220 minutes

--------------------------------------------------------------------

Which program is overall faster?

Program A:

Operate: O(n)

Output: O(n)

Program B:

Operate: O(1)

Output: O(n^2)

a. Program A: Correct answer

Except in the case where n = 1 (they would be equal) n^2 > n and as n-> infinity, program A, 3x O(n), is < program B, 2x O(1) + O(n^2). Removing the insignificant as n-> infinity: O(n)<O(n^2)

b. Program B

c. They are the same

--------------------------------------------------------------------

Which Greek letter is most important for comparing algorithms?

a. O(n): Correct answer

b. o(n)

c. Ω(n)

d. Θ(n)

e. ω(n)