Understanding Algorithmic Complexity

Study Notes

Algorithmic complexity measures the resources an algorithm needs to solve a problem.
It is used to compare algorithm efficiency and predict performance as input grows.

Time complexity measures how long an algorithm takes to run based on input size.
Big O notation expresses the upper bound of the growth rate.
Common time complexities include:
- O(1) Constant Time: Same time regardless of input size.
- O(log n) Logarithmic Time: Time increases logarithmically with input size.
- O(n) Linear Time: Time increases linearly with input size.
- O(n log n) Log-Linear Time: Time increases proportionally to n times the logarithm of n.
- O(n^2) Quadratic Time: Time increases quadratically with input size.
- O(2^n) Exponential Time: Time increases exponentially with input size.

Space complexity measures the memory space an algorithm needs based on input size.
It's expressed using Big O notation.
Common space complexities include:
- O(1) Constant Space: Constant memory regardless of input size.
- O(n) Linear Space: Linear memory with input size.
- O(n^2) Quadratic Space: Quadratic memory with input size.

Big O notation describes the asymptotic behavior of functions.
In computer science, it classifies algorithms by how running time or space grows with input size.
Rules for determining Big O complexity:
- Ignore constant factors: O(2n) becomes O(n).
- Ignore lower order terms: O(n^2 + n) becomes O(n^2).
- Consider the worst-case scenario: Analyze the maximum operations the algorithm might perform.

Operation Complexities:
- Best-case: O(1)
- Average-case: O(n)
- Worst-case: O(n)
- Space complexity: O(1)

Operation Complexities:
- Best-case: O(1)
- Average-case: O(log n)
- Worst-case: O(log n)
- Space complexity: O(1)

The table showing data structure operations and complexities show various data structure, operations, and Best/Average/Worst case operations
Examples include Array, Linked List, stack, queue, Binary search tree, hash table etc

Understanding algorithmic complexity is essential for designing efficient and scalable software.
Analyzing time and space complexity helps developers choose algorithms for different tasks.