Data Structures and Algorithms

by Albert Major

Algorithmic Complexity

1. Context and Relevance

• Algorithmic complexity is a core concept in computer science and computational problem solving.
• Although it is not included in the midterm, it will be on the final exam in June and the resit in July.
• It is especially important in the upcoming block, where the focus will shift to designing efficient algorithms.
• Understanding complexity allows us to compare different algorithms not just based on correctness, but also on their performance as input size increases.

2. What is Algorithmic Complexity?

• It provides a formal way to analyze how the resource requirements of an algorithm grow with respect to the input size.
• Two main types of resource consumption are considered:
  • Time complexity: How the running time of the algorithm changes as the size of the input grows.
  • Space complexity: How the memory usage of the algorithm changes with input size.
• In modern computing, space complexity is often less critical due to large memory availability, unless extremely large datasets are involved.

3. Worst-Case Analysis

• Worst-case complexity is the standard approach unless otherwise specified.
• This approach ensures that we evaluate the maximum time or space an algorithm will require for inputs of a given size.
• While best-case and average-case scenarios can be informative, worst-case is the most reliable and safe metric for comparing algorithms.

4. Big O Notation

• The most common mathematical notation used to describe algorithmic complexity.
• Denoted as: O(f(n)), where:
  • n is the size of the input.
  • f(n) is a function that describes how the running time (or space) grows as a function of n.