IMG_7089.jpeg

# Algorithmic Complexity ## What is Algorithmic Complexity? Algorithmic complexity is a measure of how much time (time complexity) and space (space complexity) resources are required by an algorithm for an arbitrary input size. - Complexity is expressed using **Big O notation**. - It focuses on t...

# Algorithmic Complexity ## What is Algorithmic Complexity? Algorithmic complexity is a measure of how much time (time complexity) and space (space complexity) resources are required by an algorithm for an arbitrary input size. - Complexity is expressed using **Big O notation**. - It focuses on the **dominant** term, ignoring constants and lower-order terms. - It describes the **growth rate** of resource usage as the input size increases. ### Time Complexity **Time complexity** refers to the amount of time taken by an algorithm to run as a function of the length of the input. ### Space Complexity **Space complexity** refers to the amount of memory space required by an algorithm, as a function of the length of the input. It includes space for the input data and auxiliary space. ## Common Complexities The following table lists common complexities in order of increasing growth rate: | Notation | Name | Description | Example | | :------- | :------------- | :------------------------------------------------------------------------------------------------------------- | :---------------------------------------------------------------------------------------------------- | | O(1) | Constant | The execution time (or space) is the same for all input sizes. | Accessing an element in an array by index. | | O(log n) | Logarithmic | The execution time increases logarithmically with the input size. | Binary search. | | O(n) | Linear | The execution time increases linearly with the input size. | Searching an unsorted list. | | O(n log n)| Linearithmic | The execution time increases linearly but is also affected by a logarithmic factor. | Merge sort, heap sort. | | O(n^2) | Quadratic | The execution time increases quadratically with the input size. | Bubble sort, insertion sort. | | O(n^3) | Cubic | The execution time increases cubically with the input size. | Matrix multiplication. | | O(2^n) | Exponential | The execution time doubles with each additional element in the input size. | Finding all subsets of a set. | | O(n!) | Factorial | The execution time increases factorially with the input size, representing the product of all integers up to n. | Finding all permutations of a string. | ## Visual Representation The image shows a graph comparing the growth rates of different time complexities: - **X-axis:** Input Size (n) - **Y-axis:** Number of Operations The graph plots the following complexities: - O(1) - Constant (horizontal line) - O(log n) - Logarithmic (slowly increasing curve) - O(n) - Linear (straight line) - O(n log n) - Linearithmic (slightly steeper curve than linear) - O(n^2) - Quadratic (steeper curve) - O(2^n) - Exponential (very steep curve) The graph visually demonstrates how the number of operations increases with input size for each complexity class. Lower complexity classes (like constant and logarithmic) grow much slower than higher complexity classes (like quadratic and exponential).