Algorithmic Complexity

Algorithmic Complexity

• A measure of the time and space an algorithm requires in relation to the input size.
• Expressed using Big O notation.

Time Complexity

• Represents the amount of time an algorithm takes to run as a function of the input length.

Calculating Time Complexity

• Determine the input that affects the algorithm's performance.
• Identify the code segment that most significantly impacts performance.
• Create a function that represents how run time depends on the input.
• Simplify the function to Big O notation.

Common Complexities

• Constant: $O(1)$
• Logarithmic: $O(log n)$
• Linear: $O(n)$
• Linearithmic: $O(n log n)$
• Quadratic: $O(n^2)$
• Cubic: $O(n^3)$
• Polynomial: $O(n^k)$
• Exponential: $O(2^n)$
• Factorial: $O(n!)$

Space Complexities

• Constant: $O(1)$
• Linear: $O(n)$
• Quadratic: $O(n^2)$

Examples of Time complexity

• print_items(n) with a single loop: $O(n)$ (Linear Time)
• print_items(n) with a loop that happens 3 times: $O(1)$ (Constant Time)
• print_items(n) with nested loops: $O(n^2)$ (Quadratic Time)
• print_items(n) with one loop and one nested loop: $O(n^2)$
• print_items(a, b) with two independent loops: $O(a + b)$

Importance

• Helps estimate the resources needed as input grows.
• Aids in comparing different solutions.
• Used to choose the most efficient algorithm.