سوال ۶۸ کنکور ارشد علوم کامپیوتر ۱۴۰۱

Read the keyword. The phrase "at least of order $f$" describes a lower bound on the resource (time or memory). We need the notation whose meaning is "grows no slower than $f$ (up to a constant), for large $n$."

The five families. For functions on $\mathbb{N}$ into $\mathbb{R}^{+}$:

Match. "At least order $f$" means the cost is bounded below by a constant multiple of $f$:

$g(n) \in \Omega(f(n)) \iff \exists\, c > 0,\, n_0 : \; g(n) \ge c\, f(n) \ \text{ for all } n \ge n_0.$

This is exactly the big-Omega ($\Omega$) notation, which is option (2).

Why not the others?

• $O$ and $o$ give upper bounds ("at most"), the opposite of "at least."
• $\omega$ is a strict lower bound ("strictly faster"); "at least" allows equality of rate, so the non‑strict $\Omega$ is the correct, general choice.

Exam trick: Capital $O$/$\Omega$/$\Theta$ are the non‑strict ("$\le$ / $\ge$ / $=$") bounds; lowercase $o$/$\omega$ are the strict ("$<$ / $>$") ones. "At least" $\Rightarrow$ lower bound $\Rightarrow$ $\Omega$.