🗂️ Introduction to Algorithm Analysis

What is an Algorithm?

An algorithm is a step-by-step procedure or set of rules to solve a specific problem or perform a task. In programming, algorithms are the backbone of software, enabling tasks like searching, sorting, or data processing.

• Examples:
  • Finding a number in a list (searching).
  • Arranging numbers in order (sorting).
• Importance: Efficient algorithms save time and resources, especially for large datasets.

Why Analyze Algorithms?

Analyzing algorithms helps us understand their efficiency in terms of:

• Time: How long the algorithm takes to complete as input size grows.
• Space: How much memory the algorithm uses relative to input size.

This analysis is critical for:

• Selecting the best algorithm for a problem.
• Ensuring scalability for large inputs.
• Optimizing code for better performance.

Time vs. Space Complexity

• Time Complexity: Measures how the running time of an algorithm increases with input size (denoted by $n$ ).
• Space Complexity: Measures how much memory an algorithm requires as input size grows.
• Both are expressed using Big O notation, which focuses on the worst-case growth rate.

Big O Notation

Definition

Big O notation describes the upper bound of an algorithm’s growth rate, indicating how its time or space requirements scale with input size.