1. Algorithm Complexity → No of operations in the CPU

Algorithm complexity refers to the amount of computational resources (time or space) that an algorithm uses as the input size grows. The two key types of complexity are:

• Time complexity: How the runtime of an algorithm increases with the input size.
• Space complexity: How the memory usage of an algorithm increases with the input size.

2. Big O Notation

Big O notation is a mathematical way to describe the upper limit of an algorithm's complexity as the input size increases. It gives you a high-level understanding of how an algorithm performs with large inputs, helping you compare different algorithms.

Common Big O Notations:

• O(1) – Constant Time: The algorithm's performance is the same regardless of input size.
• O(log n) – Logarithmic Time: The algorithm's performance increases logarithmically as the input size grows (e.g., binary search).
• O(n) – Linear Time: The performance increases linearly with input size (e.g., iterating through an array).
• O(n log n) – Log-linear Time: Found in more efficient sorting algorithms like merge sort.
• O(n²) – Quadratic Time: Performance increases quadratically as input size grows (e.g., bubble sort, insertion sort for nested loops).
• O(2ⁿ) – Exponential Time: Performance doubles with each additional element (e.g., recursive algorithms that solve the Fibonacci sequence).
• O(n!) – Factorial Time: Extremely slow-growing complexity found in algorithms that check all permutations (e.g., traveling salesperson problem).

3. Different Cases in Complexity

When analyzing an algorithm, you should consider the best, worst, and average-case scenarios, depending on how the input is structured.

3.1 Worst-case complexity (Big O notation):

This tells you the maximum time an algorithm could take given the worst possible input. This is the most commonly analyzed case, as it sets an upper bound.

• Example: In a linear search, the worst-case time complexity is O(n), because the element might be found at the very end of the list.

3.2 Best-case complexity (Ω notation):