CMSC 132 Final Study Exam With 100% Correct Answers 2024

Analyzing runtime Insert element into position 0 of an array of size n (in java) - ANSRuns in linear time, (if the array is size n and you double it, time will be doubles as well, this is a good way to think about linear time). Analyzing runtime Retrieving an element from an array of size n (at a particular index, in java). - ANSWhen the CPU has to do the arithmetic to get the element from the specified index, it's a constant time operation. The arithmetic barley takes any time regardless of what index it is asking for. (note: the size of arrays in java are bounded to 2^32) Analyzing runtime Program that prints all of the n-digit numbers - ANSIt is an exponential function multiplied by a linear function. Think about 2 parabolas where one is shallow and the other is steep. Can we make the shallow one worse than the steep one by multiplying it by a large constant? - ANS- Yes, all parabolas are in the same "ballpark." - It doesn't matter if one parabola starts better by the other, if you multiply it by a big enough number, it is the same thing. Imagine a parabola and a shallow line where the line is clearly faster, what if we start multiplying it? will the line still be better? - ANS- Multiplying does slow it down but even when we multiply by a large number, after the crossover we still see that the red line is faster. - As n goes to infinity, there is no way u can multiply the line by a number and make it worse. - Conclusion: lines are better/faster than parabolas. f(n) as O(g(n)) means: - ANSAs n goes toward infinity, f is either better, (faster/smaller) than g, or "in the same ballpark." What does "In the same ballpark" mean? - ANS- Even though g might seem better (smaller), we can multiply it by a big number and make it worse (bigger) than f(for big values of n). - We can find a big enough value m, so that f(n) < mg(n) for sufficiently large n. On a test Fawzi may ask: show 3n^2 + 15n + 20 is O(n^2) How would you show that? - ANS- Determine what number to multiply by n^2 to show that it can be worse than the first function. - answer: "I choose the multiplier n = 4, now 3n^2 + 15n + 20 < m(n^2) as long as n > 20. Show 100n + 150 is O(n) - ANS- Keep plugging numbers into n until you could prove the answer is true. - I choose m = 101 - Now 100n + 150 < m(n) as long as n > 1000 What is the big O of the binary search algorithm? - ANSO(log n) If f is linear and g is quadratic, - ANSthen f is O(g) but g is NOT O(f) If f is linear and g is logarithmic, - ANSthen f is NOT O(g) but g IS O(f) if f(n) = 2^n and g(n) = 3^n, - ANSthen f is O(g) but g is not O(f) f is O(g) meaning - ANS- f is either better (smaller) than g or at least not dramatically worse. - this is big O notation f is o(g) meaning - ANSf is dramatically better (smaller) than g. Suppose we have two functions, f(n) and g(n), and we want to know: Are they "in the same ballpark"? if not, which one is better/worse? evaluate this limit: lim (f(n)/g(n)) n --> infinity What does it mean if this limit comes out as 0? - ANSIf this limit comes out as zero that means whatever is in the denominator is getting bigger dramatically faster than whatever is on top, so f is faster. We can write this in little o notation: f(n) is o(g(n)) Suppose we have two functions, f(n) and g(n), and we want to know: Are they "in the same ballpark"? if not, which one is better/worse? evaluate this limit: lim (f(n)/g(n)) n --> infinity What does it mean if this limit diverges? (goes to infinity) - ANSIf the limit diverges (goes to infinity) f is growing much faster so in little o notation we would write: g(n) is o(f(n)) Suppose we have two functions, f(n) and g(n), and we want to know: Are they "in the same ballpark"? if not, which one is better/worse? evaluate this limit: lim (f(n)/g(n)) n --> infinity What does it mean if this limit equals a non zero constant? - ANSf(n) is theta(g(n)) (check lecture 40 for theta notation) Analyzing code fragments for (int i= 0; i< n; i++) { Sln("Hi"); } - ANSO(n) Analyzing code fragments for (int i= 0; i< 100 * n; i++) { Sln("HI"); } - ANSO(n) Analyzing code fragments for (int i= 0; i< n; i++) { for (int j = 0; j < n; j++) { Sln("HI"); } } - ANSO(n^2) Analyzing code fragments for (int i= 0; i< n; i++) { for (int j = i; j < n; j++) { Sln("HI"); } } - ANSO(n^2) - represents gauss' formula Analyzing code fragments for (int i= n; i> 1 ; i/= 2) { Sln("HI"); } - ANSO(log n) Analyzing code fragments void foo() {...} // Takes time O(