Design and Analysis of Algorithms 2023/2024

These flashcards cover key concepts, definitions, and important terms from the lecture on Design and Analysis of Algorithms.

Asymptotic Notation

A method for describing the limiting behavior of a function, particularly in computer science for analyzing the efficiency of algorithms.

Θ(g(n))

The set of functions that grow at the same rate as g(n), bounded above and below by constant multiples of g(n) for sufficiently large n.

O(g(n))

The set of functions f(n) that grow at most at the rate of g(n), bounded above by a constant multiple of g(n) for sufficiently large n.

Ω(g(n))

The set of functions f(n) that grow at least at the rate of g(n), bounded below by a constant multiple of g(n) for sufficiently large n.

Master Theorem

A method for analyzing the time complexity of divide-and-conquer algorithms represented by recurrences of the form T(n) = aT(n/b) + f(n).

Recurrence Relation

An equation that recursively defines a sequence: each term is defined as a function of preceding terms.

Regularity Condition

A requirement in the Master Theorem where af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n.

T(n) = aT(n/b) + f(n)

The standard form of a recurrence relation used in the Master Theorem for solving time complexity.

Closed Form

An explicit formula that allows for the computation of the terms of a sequence without requiring recursion.

Practice Problems

Exercises designed to apply theoretical knowledge, in this case, to find closed forms for given recurrences.