Learn Big O Notation in German: 44 Flashcards on Landau-Notation, Schranken and Sorting Costs

Deck EB6164 – Big-O-Notation is the German edition of our Big O notation study guide. It has the same 44 cards. The fronts are in English, the way you'll see them in interviews and documentation, and every answer is in German. That makes it useful if you study computer science at a German-speaking university, or if you need to explain an algorithm's cost in German.

Eight cards from the deck

What you'll memorize

Klassen: konstante Zeit O(1), logarithmisch O(log n), linear O(n), linearithmisch O(n log n), O(n²), naive Matrixmultiplikation O(n³), exponentiell O(2ⁿ), polylogarithmisch, superpolynomiell, subexponentiell, inverse Ackermann-Funktion α(n). Notationen: Little-o, Big Omega (Ω), Big Theta (Θ), asymptotische Äquivalenz (~), Soft-O (Õ), Vinogradovs ≪, Knuth. Algorithmen: binäre Suche, lineare Suche, Quicksort, Mergesort, Bubblesort, Insertionsort, Dijkstra mit Binärheap, Bellman-Ford, Floyd-Warshall. Begriffe: Platzkomplexität, in-place, amortisierte Laufzeit, bester, durchschnittlicher und schlechtester Fall, Grenzverhalten, Union-Find.

Learn the German vocabulary

Use the German name for the notation. German lecture notes rarely say "Big O". They call it Landau-Notation or Landau-Symbole, after Edmund Landau, who made Paul Bachmann's O from 1894 widely known. The deck never uses either term, so add them to the hint of card 1. Then learn the three bounds as a set: obere Schranke (O), untere Schranke (Ω) and scharfe Schranke (Θ). Practise a full sentence until it comes easily, for example: „Quicksort liegt im schlechtesten Fall in O(n²)". In German you say an algorithm liegt in a class, not that it is one.

Fix these cards. Two errors are shared with the other editions, and one is only in the German deck:

• Card 15 answers „O(n log n) im Durchschnittsfall". The real fact is a lower bound: every comparison sort needs Ω(n log n) Vergleiche im schlechtesten Fall (and on average). Rewrite the card with Ω.
• Card 25 says polylogarithmic time is „langsamer als logarithmisch". That is wrong. For k > 1, (log n)^k grows faster than log n and slower than any polynomial. Change it to „schneller als logarithmisch, aber langsamer als jedes Polynom".
• Card 3 should read f(n) with a lowercase f. Pair it with card 30 so you remember that = really means f ∈ O(g).

Other editions

To compare the cards with explanations in another language, read the English original or the Spanish edition. Search for EB6164 in the Flip It library to start studying.