Big-O Notation — Data Structures Übungsblatt

Grades 11–12 / College Schwerer Schwierigkeitsgrad 10 Aufgaben

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.

Geübte Fähigkeiten

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

Name: Datum: Stunde:

Übungsblatt: Big-O Notation

Anleitung: Löse jede Aufgabe sorgfältig. Zeige deine Arbeit klar. Schreibe deine endgültige Antwort in das vorgesehene Feld oder wie angewiesen auf ein separates Blatt.

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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

Big-O Notation — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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 — Übungsblatt (Fortsetzung)

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

Big-O Notation — Übungsblatt (Fortsetzung)

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.

Lösungsschlüssel

1.

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

Endgültige Antwort: $O(n^3)$
2.

Endgültige Antwort: $\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)$ .

Endgültige Antwort: $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)$ .

Endgültige Antwort: True
5.

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

Endgültige Antwort: (A) $O(n^2)$ and $\Omega(n^2)$

Lösungsschlüssel (Fortsetzung)

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)$ .

Endgültige Antwort: $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))$ .

Endgültige Antwort: $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)$ .

Endgültige Antwort: (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)$ .

Endgültige Antwort: 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)$ .

Endgültige Antwort: $O(n)$

PDF herunterladen

Häufige Fehler, die es zu vermeiden gilt

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ⁿ)

Erstelle dein eigenes Arbeitsblatt

Möchtest du neue big-o notation-Aufgaben in deiner gewünschten Schwierigkeit? Nutze WorksheetSmith, um in Sekunden ein individuelles, druckfertiges PDF zu erstellen.

Individuelles Big-O Notation-Arbeitsblatt erstellen

Zuletzt aktualisiert: 2026

Die WorksheetSmith-Arbeitsblatt-App öffnen