,
, CS 5800 Midterm Exam Study Guide |
Algorithms Practice Problems & Solutions |
Northeastern University | 2026/2027 update.
SECTION 1: ASYMPTOTIC NOTATION & ANALYSIS
(Questions 1–10)
1. Which of the following statements is TRUE about asymptotic
notation?
A) O ( f ( n )) represents a lower bound on f ( n )
B) Θ ( f ( n )) means f ( n )is both O ( f ( n )) and Ω ( f ( n ) )
C) Ω ( f ( n ) )represents an upper bound on f ( n )
D) O ( f ( n )) and Ω ( f ( n ) )are always equal
Correct Answer: B
Rationale: Θ ( f ( n )) (Theta notation) represents a tight bound, meaning the
function is bounded both above and below by f ( n )asymptotically. O notation
represents an upper bound (not lower), and Ω represents a lower bound (not
upper).
Source: CS 5800 Homework 1 Asymptotic Analysis
2. Is 22 n=O ( 2n )?
A) True
B) False
C) True only for small n
D) Cannot be determined
Correct Answer: B
n
Rationale: 22 n=( 22 ) =4 n. Since 4 ngrows significantly faster than 2n , 22 nis NOT
O ( 2 ). In fact, 2 =Ω ( 2 ) but not O ( 2 ).
n 2n n n
, CS 5800 Midterm Exam Study Guide |
Algorithms Practice Problems & Solutions |
Northeastern University | 2026/2027 update.
SECTION 1: ASYMPTOTIC NOTATION & ANALYSIS
(Questions 1–10)
1. Which of the following statements is TRUE about asymptotic
notation?
A) O ( f ( n )) represents a lower bound on f ( n )
B) Θ ( f ( n )) means f ( n )is both O ( f ( n )) and Ω ( f ( n ) )
C) Ω ( f ( n ) )represents an upper bound on f ( n )
D) O ( f ( n )) and Ω ( f ( n ) )are always equal
Correct Answer: B
Rationale: Θ ( f ( n )) (Theta notation) represents a tight bound, meaning the
function is bounded both above and below by f ( n )asymptotically. O notation
represents an upper bound (not lower), and Ω represents a lower bound (not
upper).
Source: CS 5800 Homework 1 Asymptotic Analysis
2. Is 22 n=O ( 2n )?
A) True
B) False
C) True only for small n
D) Cannot be determined
Correct Answer: B
n
Rationale: 22 n=( 22 ) =4 n. Since 4 ngrows significantly faster than 2n , 22 nis NOT
O ( 2 ). In fact, 2 =Ω ( 2 ) but not O ( 2 ).
n 2n n n
