Algorithmic Complexity

Algorithmic Complexity

• Measures the resources needed to run an algorithm.

Time Complexity

• Measures the amount of time required for an algorithm to execute.

Big O Notation

• Describes the upper bound of time complexity, representing the worst-case scenario.
• $O(1)$ (Constant Time): Execution time is independent of input size.
• $O(log n)$ (Logarithmic Time): Execution time increases logarithmically with input size.
• $O(n)$ (Linear Time): Execution time increases linearly with input size.
• $O(n log n)$ (Linearithmic Time): Execution time increases linearly and logarithmically with input size.
• $O(n^2)$ (Quadratic Time): Execution time increases quadratically with input size.
• $O(2^n)$ (Exponential Time): Execution time doubles with each addition to the input size.
• $O(n!)$ (Factorial Time): Execution time is a factorial function of the input size.

Space Complexity

• Measures the amount of memory space required for an algorithm to execute.

Auxiliary Space

• Refers to the extra space temporarily used by an algorithm.
• Example: Copying an array to another and sorting it results in $O(n)$ space complexity and $O(n)$ auxiliary space.

Common Data Structure Operations

• Array: Insertion $O(n)$, Deletion $O(n)$, Search $O(n)$
• Linked List: Insertion $O(1)$, Deletion $O(1)$, Search $O(n)$
• Stack: Insertion $O(1)$, Deletion $O(1)$, Search $O(n)$
• Queue: Insertion $O(1)$, Deletion $O(1)$, Search $O(n)$
• Binary Search Tree: Insertion $O(log n)$, Deletion $O(log n)$, Search $O(log n)$
• Hash Table: Insertion $O(1)$, Deletion $O(1)$, Search $O(1)$

Common Sorting Algorithms

• Bubble Sort: Best $O(n)$, Average $O(n^2)$, Worst $O(n^2)$, Space $O(1)$
• Insertion Sort: Best $O(n)$, Average $O(n^2)$, Worst $O(n^2)$, Space $O(1)$
• Selection Sort: Best $O(n^2)$, Average $O(n^2)$, Worst $O(n^2)$, Space $O(1)$
• Merge Sort: Best $O(n log n)$, Average $O(n log n)$, Worst $O(n log n)$, Space $O(n)$
• Quick Sort: Best $O(n log n)$, Average $O(n log n)$, Worst $O(n^2)$, Space $O(log n)$
• Heap Sort: Best $O(n log n)$, Average $O(n log n)$, Worst $O(n log n)$, Space $O(1)$
• Counting Sort: Best $O(n + k)$, Average $O(n + k)$, Worst $O(n + k)$, Space $O(k)$
• Radix Sort: Best $O(nk)$, Average $O(nk)$, Worst $O(nk)$, Space $O(n + k)$
• $k$ represents the range of the input.
• Quick sort generally performs best in practice despite having a $O(n^2)$ worst-case time complexity.
• Merge sort guarantees a $O(n log n)$ time complexity.
• Counting and Radix sorts are linear time algorithms but are limited by the range of input values.