Data Structures & Algorithms Foundations & Complexity Analysis Syllabus

Foundations & Complexity Analysis syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Foundations & Complexity Analysis in Data Structures & Algorithms, not a summary of it.

1. 1

   Algorithm Analysis Fundamentals

   4 topics

   • Asymptotic Notation
   • Time Complexity
   • Space Complexity
   • Amortized Analysis
2. 2

   Mathematical Preliminaries

   4 topics

   • Discrete Math Basics
   • Modular Arithmetic
   • Number Theory Essentials
   • Probability for Algorithms
3. 3

   Recursion & Mathematical Induction

   4 topics

   • Recursion Fundamentals
   • Recurrence Relations
   • Solving Recurrences
   • Tail Recursion and Optimization
4. 4

   Bit Manipulation

   4 topics

   • Bitwise Operators
   • Bit Masking Techniques
   • Common Bit Tricks
   • Counting Set Bits

Foundations & Complexity Analysis flashcards for Data Structures & Algorithms

21 of 52 cards from the Foundations & Complexity Analysis deck — real questions with worked answers.

1. What does Big-O notation $O(g(n))$ formally represent?

   An asymptotic upper bound. $f(n) = O(g(n))$ means there exist constants $c > 0$ and $n_0 > 0$ such that $0 \leq f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

2. Define Big-Omega notation $\Omega(g(n))$.

   An asymptotic lower bound. $f(n) = \Omega(g(n))$ means there exist constants $c > 0$ and $n_0$ such that $0 \leq c \cdot g(n) \leq f(n)$ for all $n \geq n_0$.

3. Define Big-Theta notation $\Theta(g(n))$.

   A tight asymptotic bound. $f(n) = \Theta(g(n))$ iff $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, i.e. $c_1 g(n) \leq f(n) \leq c_2 g(n)$ for large $n$.

4. How do little-o $o(g(n))$ and little-omega $\omega(g(n))$ differ from Big-O and Big-Omega?

   They denote strict (non-tight) bounds. $f = o(g)$ means $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$; $f = \omega(g)$ means $\lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$.

5. Order these common complexity classes from fastest-growing to slowest-growing: $n!$, $2^{n}$, $n^{2}$, $n\log n$, $\log n$, $n$, $1$.

   $n! > 2^{n} > n^{2} > n\log n > n > \log n > 1$.

6. In asymptotic analysis, why can constant factors and lower-order terms be dropped from $3n^{2} + 5n + 7$?

   For large $n$ they are dominated by the leading term, so the growth rate is $\Theta(n^{2})$. Asymptotic notation describes behavior as $n \to \infty$.

7. What is the difference between worst-case, average-case, and best-case time complexity?

   Worst-case = maximum running time over all inputs of size $n$; average-case = expected time over a distribution of inputs; best-case = minimum running time. Big-O usually refers to the worst case.

8. What time complexity does a simple binary search on a sorted array have, and why?

   $O(\log n)$, because each comparison halves the remaining search space: $n \to \frac{n}{2} \to \frac{n}{4} \to \cdots \to 1$ takes $\log_2 n$ steps.

9. Define space complexity and distinguish auxiliary space from total space.

   Space complexity is the total memory an algorithm uses as a function of input size. Auxiliary space excludes the input itself and counts only the extra working memory allocated.

10. What is the space complexity of a recursive algorithm, ignoring heap allocations?

    It is $O(d)$ where $d$ is the maximum recursion depth, because each active call frame occupies stack space until it returns.

11. What is amortized analysis?

    A technique that averages the cost of a sequence of operations over the whole sequence, so that occasional expensive operations are spread out, giving a realistic per-operation cost even when individual operations vary.

12. Name the three standard methods of amortized analysis.

    The aggregate method, the accounting (banker's) method, and the potential method.

13. Why is appending to a dynamic array (doubling on resize) $O(1)$ amortized despite occasional $O(n)$ resizes?

    Doubling means resizes cost $1 + 2 + 4 + \cdots + n \approx 2n$ total across $n$ inserts, so the average per insertion is $\frac{2n}{n} = O(1)$ amortized.

14. In the potential method, how is the amortized cost $\hat{c_i}$ of an operation defined?

    $\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$, where $c_i$ is the actual cost and $\Phi$ is the potential function of the data structure before and after.

15. State De Morgan's laws for logic.

    $\lnot(p \land q) \equiv \lnot p \lor \lnot q$ and $\lnot(p \lor q) \equiv \lnot p \land \lnot q$.

16. What is the sum of the first $n$ positive integers?

    $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

17. What is the formula for the number of subsets and the number of $k$-element subsets of an $n$-element set?

    Total subsets: $2^{n}$. Subsets of size $k$: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

18. State the Pigeonhole Principle.

    If $n$ items are placed into $m$ containers with $n > m$, then at least one container holds at least $\lceil \frac{n}{m} \rceil \geq 2$ items.

19. State the Inclusion-Exclusion Principle for two sets.

    $|A \cup B| = |A| + |B| - |A \cap B|$.

20. What is the closed form for a finite geometric series $\sum_{i=0}^{n-1} r^{i}$ with $r \neq 1$?

    $\sum_{i=0}^{n-1} r^{i} = \frac{r^{n} - 1}{r - 1}$.

21. Define the modulo operation and state the range of $a \bmod n$ for positive $n$.

    $a \bmod n$ is the remainder of $a$ divided by $n$. For $n > 0$ it satisfies $0 \leq (a \bmod n) < n$.

See more Foundations & Complexity Analysis flashcards →

Planning Foundations & Complexity Analysis for Data Structures & Algorithms

Foundations & Complexity Analysis (Data Structures & Algorithms) FAQ