Big-O Notation — Fiche d'exercices de Data Structures

Grades 11–12 / College Difficulté difficile 10 problèmes

Big-O notation describes how an algorithm's runtime or space grows as input size n increases. It focuses on worst-case asymptotic behavior and ignores constants and lower-order terms.

Common classes from fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential.

Examples: array index access O(1); binary search O(log n); linear scan O(n); nested loops over n O(n²); recursive Fibonacci without memo O(2ⁿ). Choose data structures to match operation needs.

Compétences travaillées

Classifying algorithms by Big-O
Comparing growth rates
Analyzing loops and nested loops
Connecting structure choice to complexity

Nom : Date : Période :

Fiche d'exercices : Big-O Notation

Consignes : Résous chaque problème avec soin. Montre clairement tout ton travail. Écris ta réponse finale dans l'espace prévu ou sur une feuille séparée comme indiqué.

1.Determine the Big-O complexity of the following function: $f(n) = 3n^3 + 2n^2 + 5n + 1$ . Provide a brief justification.

Big-O Notation — Fiche d'exercices (suite)

2.Sort the following functions in increasing order of asymptotic growth rate (from slowest to fastest): $n \log n$ , $2^n$ , $n^2$ , $\log n$ , $n!$ , $n$ , $n^{0.5}$ . Write your final ordering.

Big-O Notation — Fiche d'exercices (suite)

3.
Consider the following code fragment:
```
for i = 1 to n:
    for j = 1 to i:
        print(i + j)
```
What is the Big-O time complexity of this code? Explain your reasoning.

Big-O Notation — Fiche d'exercices (suite)

4.True or False: $2^{n+1} = O(2^n)$ . Justify your answer.

Big-O Notation — Fiche d'exercices (suite)

5.Multiple Choice: Which of the following is equivalent to $\Theta(n^2)$ ?
1. A. $O(n^2)$ and $\Omega(n^2)$
2. B. $O(n^2)$ only
3. C. $\Omega(n^2)$ only
4. D. Neither $O(n^2)$ nor $\Omega(n^2)$

Big-O Notation — Fiche d'exercices (suite)

6.Determine the Big-O complexity of the recurrence $T(n) = 2T(n/2) + n$ . Assume $T(1) = 1$ . Show your work using the Master Theorem or iteration method.
7.Given $f(n) = n^2 \log n$ and $g(n) = n^2 \sqrt{n}$ , determine whether $f(n) = O(g(n))$ , $f(n) = \Omega(g(n))$ , or $f(n) = \Theta(g(n))$ . Justify your answer.

Big-O Notation — Fiche d'exercices (suite)

8.Multiple Choice: What is the Big-O complexity of the following function? \[ f(n) = \sum_{i=1}^{n} i^2 \]
1. A. $O(n)$
2. B. $O(n^2)$
3. C. $O(n^3)$
4. D. $O(\log n)$

Big-O Notation — Fiche d'exercices (suite)

9.Prove or disprove: $n^3 + 100n^2 = \Omega(n^3)$ . Provide a formal proof using the definition of Big-Omega.

Big-O Notation — Fiche d'exercices (suite)

10.Consider the algorithm that finds the maximum element in an unsorted array of size $n$ . What is the tightest asymptotic bound for its worst-case time complexity? Explain why.

Corrigé

1.

The highest-order term is $3n^3$ , so the function grows as $n^3$ . All lower-order terms are dominated.

Réponse finale : $O(n^3)$
2.

Réponse finale : $\log n$ , $n^{0.5}$ , $n$ , $n \log n$ , $n^2$ , $2^n$ , $n!$
3.

The outer loop runs $n$ times, and the inner loop runs an average of $n/2$ times, giving approximately $n^2/2$ operations, which is $O(n^2)$ .

Réponse finale : $O(n^2)$
4.

$2^{n+1} = 2 \cdot 2^n$ , so $2^{n+1} \leq c \cdot 2^n$ for $c = 2$ and all $n \geq 0$ . Thus $2^{n+1} = O(2^n)$ .

Réponse finale : True
5.

By definition, $\Theta(n^2)$ means the function is both $O(n^2)$ and $\Omega(n^2)$ .

Réponse finale : (A) $O(n^2)$ and $\Omega(n^2)$

Corrigé (suite)

6.

Using the Master Theorem with $a=2$ , $b=2$ , $f(n)=n$ , we have $\log_b a = 1$ , and $f(n) = n = \Theta(n^1)$ , so case 2 applies: $T(n) = \Theta(n \log n)$ .

Réponse finale : $O(n \log n)$
7.

Compare: $n^2 \log n$ vs $n^2 \sqrt{n} = n^{2.5}$ . Since $\log n$ grows slower than $n^{0.5}$ , $f(n)$ is asymptotically smaller, so $f(n) = O(g(n))$ but not $\Omega(g(n))$ .

Réponse finale : $f(n) = O(g(n))$
8.

The sum $\sum_{i=1}^{n} i^2 = n(n+1)(2n+1)/6$ , which is $\Theta(n^3)$ .

Réponse finale : (C) $O(n^3)$
9.

We need constants $c > 0$ and $n_0$ such that $n^3 + 100n^2 \geq c n^3$ for all $n \geq n_0$ . Choose $c = 1$ and $n_0 = 1$ : $n^3 + 100n^2 \geq n^3$ for all $n \geq 1$ . Thus $n^3 + 100n^2 = \Omega(n^3)$ .

Réponse finale : True
10.

The algorithm must examine each element once to find the maximum, requiring $n-1$ comparisons in the worst case, which is $\Theta(n)$ .

Réponse finale : $O(n)$

Télécharger le PDF

Erreurs fréquentes à éviter

Confusing best case with Big-O (usually worst case)
Calling O(2n) different from O(n) — constants drop
Ignoring hidden loops in string operations
Assuming recursion is always O(2ⁿ)

Générez la vôtre

Vous voulez un nouvel ensemble de problèmes de big-o notation à la difficulté de votre choix ? Utilisez WorksheetSmith pour compiler un PDF personnalisé prêt à imprimer en quelques secondes.

Générer une fiche personnalisée sur Big-O Notation

Dernière mise à jour : 2026

Ouvrir l'application de fiches WorksheetSmith