10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
CMSC 132 Exam review (2025) Exam Questions &
Answers | Latest Already Graded A+ UPDATE
2025|2026!! STUDY GUIDE EXAM
Save
Terms in this set (229)
Analyzing runtime Runs in linear time, (if the array is size n and you
double it, time will be doubles as well, this is a good
Insert element into way to think about linear time).
position 0 of an array of
size n (in java)
When the CPU has to do the arithmetic to get the
Analyzing runtime
element from the specified index, it's a constant time
operation. The arithmetic barley takes any time
Retrieving an element
regardless of what index it is asking for.
from an array of size n (at
a particular index, in java).
(note: the size of arrays in java are bounded to 2^32)
Analyzing runtime It is an exponential function multiplied by a linear
function.
Program that prints all of
the n-digit numbers
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 1/40
,10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
Think about 2 parabolas - Yes, all parabolas are in the same "ballpark."
where one is shallow and - It doesn't matter if one parabola starts better by the
the other is steep. other, if you multiply it by a big enough number, it is
Can we make the shallow the same thing.
one worse than the steep
one by multiplying it by a
large constant?
- Multiplying does slow it down but even when we
Imagine a parabola and a
multiply by a large number, after the crossover we still
shallow line where the line
see that the red line is faster.
is clearly faster, what if we
- As n goes to infinity, there is no way u can multiply
start multiplying it? will the
the line by a number and make it worse.
line still be better?
- Conclusion: lines are better/faster than parabolas.
As n goes toward infinity, f is either better,
f(n) as O(g(n)) means:
(faster/smaller) than g, or "in the same ballpark."
- Even though g might seem better (smaller), we can
multiply it by a big number and make it worse (bigger)
What does "In the same
than f(for big values of n).
ballpark" mean?
- We can find a big enough value m, so that f(n) <
mg(n) for sufficiently large n.
On a test Fawzi may ask: - Determine what number to multiply by n^2 to show
show 3n^2 + 15n + 20 is that it can be worse than the first function.
O(n^2) - answer: "I choose the multiplier n = 4, now 3n^2 + 15n
+ 20 < m(n^2) as long as n > 20.
How would you show
that?
- Keep plugging numbers into n until you could prove
the answer is true.
Show 100n + 150 is O(n)
- I choose m = 101
- Now 100n + 150 < m(n) as long as n > 1000
What is the big O of the O(log n)
binary search algorithm?
If f is linear and g is then f is O(g) but g is NOT O(f)
quadratic,
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 2/40
,10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
If f is linear and g is then f is NOT O(g) but g IS O(f)
logarithmic,
if f(n) = 2^n and g(n) = 3^n, then f is O(g) but g is not O(f)
- f is either better (smaller) than g or at least not
f is O(g) meaning dramatically worse.
- this is big O notation
f is o(g) meaning f is dramatically better (smaller) than g.
Suppose we have two If this limit comes out as zero that means whatever is
functions, f(n) and g(n), in the denominator is getting bigger dramatically
and we want to know: Are faster than whatever is on top, so f is faster. We can
they "in the same write this in little o notation:
ballpark"? if not, which f(n) is o(g(n))
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?
Suppose we have two If the limit diverges (goes to infinity) f is growing much
functions, f(n) and g(n), faster so in little o notation we would write:
and we want to know: Are g(n) is o(f(n))
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)
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 3/40
, 10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
Suppose we have two f(n) is theta(g(n))
functions, f(n) and g(n),
and we want to know: Are (check lecture 40 for theta notation)
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?
Analyzing code fragments O(n)
for (int i= 0; i< n; i++) {
System.out.println("Hi");
}
Analyzing code fragments O(n)
for (int i= 0; i< 100 * n; i++) {
System.out.println("HI");
}
Analyzing code fragments O(n^2)
for (int i= 0; i< n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("HI");
}
}
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 4/40
CMSC 132 Exam review (2025) Exam Questions &
Answers | Latest Already Graded A+ UPDATE
2025|2026!! STUDY GUIDE EXAM
Save
Terms in this set (229)
Analyzing runtime Runs in linear time, (if the array is size n and you
double it, time will be doubles as well, this is a good
Insert element into way to think about linear time).
position 0 of an array of
size n (in java)
When the CPU has to do the arithmetic to get the
Analyzing runtime
element from the specified index, it's a constant time
operation. The arithmetic barley takes any time
Retrieving an element
regardless of what index it is asking for.
from an array of size n (at
a particular index, in java).
(note: the size of arrays in java are bounded to 2^32)
Analyzing runtime It is an exponential function multiplied by a linear
function.
Program that prints all of
the n-digit numbers
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 1/40
,10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
Think about 2 parabolas - Yes, all parabolas are in the same "ballpark."
where one is shallow and - It doesn't matter if one parabola starts better by the
the other is steep. other, if you multiply it by a big enough number, it is
Can we make the shallow the same thing.
one worse than the steep
one by multiplying it by a
large constant?
- Multiplying does slow it down but even when we
Imagine a parabola and a
multiply by a large number, after the crossover we still
shallow line where the line
see that the red line is faster.
is clearly faster, what if we
- As n goes to infinity, there is no way u can multiply
start multiplying it? will the
the line by a number and make it worse.
line still be better?
- Conclusion: lines are better/faster than parabolas.
As n goes toward infinity, f is either better,
f(n) as O(g(n)) means:
(faster/smaller) than g, or "in the same ballpark."
- Even though g might seem better (smaller), we can
multiply it by a big number and make it worse (bigger)
What does "In the same
than f(for big values of n).
ballpark" mean?
- We can find a big enough value m, so that f(n) <
mg(n) for sufficiently large n.
On a test Fawzi may ask: - Determine what number to multiply by n^2 to show
show 3n^2 + 15n + 20 is that it can be worse than the first function.
O(n^2) - answer: "I choose the multiplier n = 4, now 3n^2 + 15n
+ 20 < m(n^2) as long as n > 20.
How would you show
that?
- Keep plugging numbers into n until you could prove
the answer is true.
Show 100n + 150 is O(n)
- I choose m = 101
- Now 100n + 150 < m(n) as long as n > 1000
What is the big O of the O(log n)
binary search algorithm?
If f is linear and g is then f is O(g) but g is NOT O(f)
quadratic,
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 2/40
,10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
If f is linear and g is then f is NOT O(g) but g IS O(f)
logarithmic,
if f(n) = 2^n and g(n) = 3^n, then f is O(g) but g is not O(f)
- f is either better (smaller) than g or at least not
f is O(g) meaning dramatically worse.
- this is big O notation
f is o(g) meaning f is dramatically better (smaller) than g.
Suppose we have two If this limit comes out as zero that means whatever is
functions, f(n) and g(n), in the denominator is getting bigger dramatically
and we want to know: Are faster than whatever is on top, so f is faster. We can
they "in the same write this in little o notation:
ballpark"? if not, which f(n) is o(g(n))
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?
Suppose we have two If the limit diverges (goes to infinity) f is growing much
functions, f(n) and g(n), faster so in little o notation we would write:
and we want to know: Are g(n) is o(f(n))
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)
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 3/40
, 10/29/25, 10:04 AM CMSC 132 Exam review (2025) Exam Questions & Answers | Latest Already Graded A+ UPDATE 2025|2026!! STUDY GUIDE E…
Suppose we have two f(n) is theta(g(n))
functions, f(n) and g(n),
and we want to know: Are (check lecture 40 for theta notation)
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?
Analyzing code fragments O(n)
for (int i= 0; i< n; i++) {
System.out.println("Hi");
}
Analyzing code fragments O(n)
for (int i= 0; i< 100 * n; i++) {
System.out.println("HI");
}
Analyzing code fragments O(n^2)
for (int i= 0; i< n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("HI");
}
}
https://quizlet.com/1100240705/cmsc-132-exam-review-2025-exam-questions-answers-latest-already-graded-a-update-20252026-study-guide-exam-… 4/40
