CSE373, MAT373: Analysis of Algorithms, Spring 2021 Date: March 23, 2021
Mock Midterm Exam 1 (Solution Hints)
( 6:35 PM – 7:50 PM : 75 Minutes )
• This exam will account for 20% of your overall grade.
• There are five (5) questions, worth 75 points in total. Please answer all of them.
• This is a closed book, closed notes exam. No cheat sheets are allowed.
• You are allowed to use scratch papers for your calculations.
Good Luck!
Question Parts Points
1. Asymptotic Bounds (a), (b), (c) 5 + 5 + 5 = 15
2. Recurrences. (a), (b), (c) 5 + 5 + 5 = 15
3. Cutting Rod – 12
4. Insertion Sort – 18
5. Prefix Sums (a), (b) 10 + 5 = 15
Total 75
This study source was downloaded by 100000899610689 from CourseHero.com on 09-24-2025 09:21:19 GMT -05:00
https://www.coursehero.com/file/106331785/midterm-sample-1-solpdf/
, Question 1. [ 15 Points ] Asymptotic Bounds. For each of the following statements state
whether it is True or False. You must justify each answer. Assume that all log’s are of base 2.
2
(a) [ 5 Points ] 2log n = Θ n2
(b) [ 5 Points ] n1.2 = Ω n log2 n
(c) [ 5 Points ] 22n = O (3n )
Solution Hints.
2 2
(a) We have, 2log n = 22 log n = 2log n = n2 = Θ n2
Hence, the given statement is True.
(b) We have,
n1.2 n0.2
limx→∞ n log2 n
= limx→∞ log2 n
n0.2 ln n
= (ln 2)2 limx→∞ 2 {∵ log2 n = ln 2 }
ln n
0.2n0.2−1
= (ln 2)2 limx→∞ 2 ln n {L’Hopital’s rule}
n
n0.2
= 0.1(ln 2)2 limx→∞
ln n 0.2−1
0.2n
= 0.1(ln 2)2 lim x→∞ 1 {L’Hopital’s rule}
n
= 0.02(ln 2)2 limx→∞ n0.2
= ∞≥c {where, c is any positive constant}
2
n1.2
So, = Ω n log n .
Hence, the given statement is True.
22n 4n 4 n
(c) We have, limx→∞ 3n = limx→∞ 3n = limx→∞ 3 = ∞.
So, 22n = ω (3n ).
Hence, the given statement is False.
1
This study source was downloaded by 100000899610689 from CourseHero.com on 09-24-2025 09:21:19 GMT -05:00
https://www.coursehero.com/file/106331785/midterm-sample-1-solpdf/
Mock Midterm Exam 1 (Solution Hints)
( 6:35 PM – 7:50 PM : 75 Minutes )
• This exam will account for 20% of your overall grade.
• There are five (5) questions, worth 75 points in total. Please answer all of them.
• This is a closed book, closed notes exam. No cheat sheets are allowed.
• You are allowed to use scratch papers for your calculations.
Good Luck!
Question Parts Points
1. Asymptotic Bounds (a), (b), (c) 5 + 5 + 5 = 15
2. Recurrences. (a), (b), (c) 5 + 5 + 5 = 15
3. Cutting Rod – 12
4. Insertion Sort – 18
5. Prefix Sums (a), (b) 10 + 5 = 15
Total 75
This study source was downloaded by 100000899610689 from CourseHero.com on 09-24-2025 09:21:19 GMT -05:00
https://www.coursehero.com/file/106331785/midterm-sample-1-solpdf/
, Question 1. [ 15 Points ] Asymptotic Bounds. For each of the following statements state
whether it is True or False. You must justify each answer. Assume that all log’s are of base 2.
2
(a) [ 5 Points ] 2log n = Θ n2
(b) [ 5 Points ] n1.2 = Ω n log2 n
(c) [ 5 Points ] 22n = O (3n )
Solution Hints.
2 2
(a) We have, 2log n = 22 log n = 2log n = n2 = Θ n2
Hence, the given statement is True.
(b) We have,
n1.2 n0.2
limx→∞ n log2 n
= limx→∞ log2 n
n0.2 ln n
= (ln 2)2 limx→∞ 2 {∵ log2 n = ln 2 }
ln n
0.2n0.2−1
= (ln 2)2 limx→∞ 2 ln n {L’Hopital’s rule}
n
n0.2
= 0.1(ln 2)2 limx→∞
ln n 0.2−1
0.2n
= 0.1(ln 2)2 lim x→∞ 1 {L’Hopital’s rule}
n
= 0.02(ln 2)2 limx→∞ n0.2
= ∞≥c {where, c is any positive constant}
2
n1.2
So, = Ω n log n .
Hence, the given statement is True.
22n 4n 4 n
(c) We have, limx→∞ 3n = limx→∞ 3n = limx→∞ 3 = ∞.
So, 22n = ω (3n ).
Hence, the given statement is False.
1
This study source was downloaded by 100000899610689 from CourseHero.com on 09-24-2025 09:21:19 GMT -05:00
https://www.coursehero.com/file/106331785/midterm-sample-1-solpdf/
