Dsa - Exam 1 Questions With Correct Answers (Graded A)

DSA - EXAM 1 QUESTIONS WITH
CORRECT ANSWERS



worst-case time complexity of an algorithm - Correct Answers -- the maximum time that
an algorithm will require for an input of size 'n'.
- uses Big-O notation O(n)

average case time complexity of an algorithm - Correct Answers -- the time that an
algorithm will require to execute a typical input of size 'n'.
- uses Big-Theta notation Θ(n) or θ(n)

best case time complexity of an algorithm - Correct Answers -- the minimum time that
an algorithm will require for an input of size 'n'.
- uses Big-Omega notation Ω(n)

Input n - Correct Answers -Represents the size of the input when analyzing algorithms.

Function f(n) - Correct Answers -Describes the running time of the algorithm as a
function of input size n.

Asymptotic Notation - Correct Answers -Used to describe how f(n) behaves relative to a
simpler function g(n).

Big-O Notation: f(n) = O(g(n)) - Correct Answers -- Definition: describes an upper bound
on the growth of f(n).
- Meaning: f(n) grows at most as fast as g(n) for large n.
- Formula: There exists a constant c such that f(n) ≤ c ⋅ g(n) for sufficiently large n.

Big-O Example - Correct Answers -f(n) = n
g(n) = n^2
Since f(n) ≤ c ⋅ g(n) → f(n) = O(g(n))

Big-Omega Notation: f(n) = Ω(g(n)) - Correct Answers -- Definition: describes a lower
bound on the growth of f(n).
- Meaning: f(n) grows at least as fast as g(n).
- Formula: There exists a constant c such that f(n) ≥ c ⋅ g(n) for sufficiently large n

Big-Omega Example - Correct Answers -f(n) = n^2
g(n) = n

, Since f(n) ≥ c ⋅ g(n) → f(n) = Ω(g(n))

Big-Theta Notation: f(n) = Θ(g(n)) - Correct Answers -- Definition: describes both an
upper and lower bound on f(n), thus having a tight bound.
- Meaning: f(n) grows exactly as fast as g(n) for large n.
- Condition: If f(n) = O(g(n)) AND f(n)=Ω(g(n)) → f(n) = Θ(g(n)).

Big-Theta Example - Correct Answers -f(n) = 3n^2 + 2n + 5
g(n) = n^2

Check O(g(n))? Yes, since c = 4 makes 4n^2 ≥ f(n)
Check Ω(g(n))? Yes, since c = 1 makes n^2 ≤ f(n)

Therefore, f(n) = Θ(g(n)).

Which time complexity is most critical? - Correct Answers -- The most useful is worst-
case complexity.
- Because we need to guarantee that an algorithm terminates within a specified
maximum time.

Limitations of Counting Sort - Correct Answers -- Can only be used when the range of
integers is known and limited.
- If the range of elements is too large, the size of the count array can become
excessive, leading to higher space and time requirements.

Limitations of Radix Sort - Correct Answers -- Time complexity is O(n * d), where d is
the number of digits.
- less efficient compared to algorithms like merge sort or heapsort (O(n log n)) unless d
= O(log n), making it less desirable in many cases.

If f(n) = Θ(g(n)) then is g(n) = Ω(f(n))? - Correct Answers -Given F(n) = θ(g(n)), then by
definition:
c_1 * g(n) <= f(n) <= c_2 * g(n)
thus implying that:
g(n) = Ω(f(n)) AND g(n) = O(f(n)).
Therefore, yes.

Little-o Notation: f(n) = o(g(n)) - Correct Answers -- Definition: describes a strict upper
bound on the growth of f(n).
- Meaning: f(n) grows strictly slower than g(n) as n → ∞.
- Formula: For every constant c>0, there exists an n_0 such that f(n) < c ⋅ g(n) for all n
≥ n_0.

Little-o Example - Correct Answers -f(n) = n
g(n) = n^2
f(n) = o(g(n)) because f(n) grows much slower than g(n) for large n.