WhatsApp Image 2025-04-08 at 16.50.17.jpeg
Document Details
Uploaded by AvailableCynicalRealism
Full Transcript
# 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. * **Time Complexity**: the amount of time taken by an algorithm to r...
# 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. * **Time Complexity**: the amount of time taken by an algorithm to run as a function of the length of the input. * **Space Complexity**: the amount of memory space taken by an algorithm to run as a function of the length of the input. Algorithmic complexity focuses on how the resources grow as the input size increases. It's about the trend, not the specifics. ## Why is it important? * **Performance**: Helps to understand and predict algorithm performance. * **Scalability**: Important for determining if an algorithm will be suitable for large inputs. * **Optimization**: Guides in choosing efficient algorithms and data structures. ## How to Express Complexity? We use **Big O notation** to express the complexity of an algorithm. * It provides an upper bound of the worst-case scenario. * It focuses on the dominant term (the one that grows the fastest). ### Common Complexity Classes | Notation | Name | Characteristics | Example | | :----------------- | :------------ | :--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | :------------------------------------------------- | | $O(1)$ | Constant | Execution time is constant, independent of input size. | Accessing an element in an array (by index). | | $O(\log n)$ | Logarithmic | Usually involves algorithms that divide the problem size in each step. | Binary search. | | $O(n)$ | Linear | Execution time increases linearly with the size of the input. | Simple search, traversing an array. | | $O(n \log n)$ | Log-linear | Often found in efficient sorting algorithms. | Merge sort, quicksort (average case). | | $O(n^2)$ | Quadratic | Execution time increases with the square of the input size. | Bubble sort, selection sort. | | $O(n^3)$ | Cubic | Common in matrix operations or algorithms with three nested loops. | Matrix multiplication. | | $O(2^n)$ | Exponential | Execution time doubles with each addition to the input dataset. | Finding all subsets of a set. | | $O(n!)$ | Factorial | The execution time grows factorially with the input size. | Traveling salesman problem (brute force approach). | | $O(n^n)$ | n-to-the-n | Extremely slow. | | | $O(\frac{1}{n})$ | Inverse | The larger the size of input, the faster it completes | | | $O(\sqrt{n})$ | Root n | Used mainly within searching and number theory algorithms | | | $O(\log \log n)$ | Double Log | Very rarely arises when analyzing algorithms. Example: interpolation search. | | | $O(n^c)$ | Polynomial | Where c is a constant. Includes linear, quadratic, cubic, etc. | | | $O(c^n)$ | Exponential | Where c is a constant greater than 1. | | | $O(n!)$ | Factorial | Grows faster than exponential. | | | $O(e^n)$ | e to the power of n | Grows faster than exponential. | | ## How to Determine Complexity? 1. **Identify operations**: Determine the basic operations the algorithm performs. 2. **Count operations**: Count how many times each operation is executed as a function of the input size. 3. **Determine Dominant Term**: Identify the term that grows the fastest as the input size increases. 4. **Express in Big O**: Write the complexity using Big O notation, dropping constants and non-dominant terms. ## Tips * Nested loops often indicate $O(n^2)$ or $O(n^3)$ complexity. * Divide and conquer algorithms often have $O(\log n)$ or $O(n \log n)$ complexity. * Be aware of the worst-case, average-case, and best-case scenarios. ## Conclusion Understanding algorithmic complexity is crucial for designing efficient and scalable algorithms.
