Exam (elaborations)
CMSC 132 Exam Review With 100% Correct And Verified Answers 2024
- Course
- Institution
CMSC 132 Exam Review With 100% Correct And Verified Answers 2024
[Show more]
Content preview
CMSC 132 Exam Review With 100% Correct And Verified Answers 2024Analyzing runtime Insert element into position 0 of an array of size n (in java) - Correct Answer-Runs 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). - Correct Answer-When 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 - Correct Answer-It 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? - Correct Answer-- 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? - Correct Answer-- 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: - Correct Answer-As n goes toward infinity, f is either better, (faster/smaller) than g, or "in the same ballpark."
What does "In the same ballpark" mean? - Correct Answer-- 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? - Correct Answer-- 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) - Correct Answer-- 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? - Correct Answer-O(log n)
If f is linear and g is quadratic, - Correct Answer-then f is O(g) but g is NOT O(f)
If f is linear and g is logarithmic, - Correct Answer-then f is NOT O(g) but g IS O(f)
if f(n) = 2^n and g(n) = 3^n, - Correct Answer-then f is O(g) but g is not O(f)
f is O(g) meaning - Correct Answer-- f is either better (smaller) than g or at least not dramatically worse.
- this is big O notation
f is o(g) meaning - Correct Answer-f 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? - Correct Answer-If 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) - Correct Answer-If 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? - Correct Answer-f(n) is theta(g(n))
(check lecture 40 for theta notation)
Analyzing code fragments
for (int i= 0; i< n; i++) {
System.out.println("Hi");
} - Correct Answer-O(n)
Analyzing code fragments
for (int i= 0; i< 100 * n; i++) {
System.out.println("HI");
} - Correct Answer-O(n)
Analyzing code fragments
for (int i= 0; i< n; i++) { for (int j = 0; j < n; j++) { System.out.println("HI"); } } - Correct Answer-O(n^2)
Analyzing code fragments
for (int i= 0; i< n; i++) { for (int j = i; j < n; j++) { System.out.println("HI"); } } - Correct Answer-O(n^2) - represents gauss' formula
Analyzing code fragments
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Vendarsol. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $20.29. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
76449 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now