IMG_1718.jpeg

# Algorithmic Time Complexity ## What is Time Complexity? Time complexity is a way to express the amount of time it takes for an algorithm to run as a function of the input size. It focuses on how the execution time grows as the input grows, not the exact time in seconds or milliseconds. ### Why i...

# Algorithmic Time Complexity ## What is Time Complexity? Time complexity is a way to express the amount of time it takes for an algorithm to run as a function of the input size. It focuses on how the execution time grows as the input grows, not the exact time in seconds or milliseconds. ### Why is it important? - **Algorithm Comparison:** Helps compare the efficiency of different algorithms for solving the same problem. - **Scalability:** Indicates how well an algorithm will perform as the input size increases. - **Performance Optimization:** Identifies bottlenecks in the code and areas for improvement. ## Common Time Complexities | Time Complexity | Big O Notation | Description | Example | | :-------------- | :------------- | :---------------------------------------------------------- | :------------------------------------------------------------------- | | Constant | O(1) | Execution time remains constant regardless of input size. | Accessing an element in an array by index. | | Logarithmic | O(log n) | Execution time increases logarithmically with input size. | Binary search. | | Linear | O(n) | Execution time increases linearly with input size. | Searching for an element in an unsorted array. | | Linearithmic | O(n log n) | Execution time increases linearly and logarithmically. | Merge sort, quicksort (average case). | | Quadratic | O(n^2) | Execution time increases quadratically with input size. | Nested loops iterating over all pairs of elements in an array. | | Cubic | O(n^3) | Execution time increases cubically with input size. | Three nested loops iterating over all triplets of elements in an array | | Exponential | O(2^n) | Execution time doubles with each addition to input size. | Recursive calculation of Fibonacci numbers. | | Factorial | O(n!) | Execution time increases dramatically with input size. | Generating all permutations of a set. | ## Big O Notation Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is used to classify algorithms according to their time or space complexity. ### Key Points - It focuses on the **upper bound** of the execution time. - It ignores constant factors and lower-order terms. - It provides a simplified way to express the growth rate of an algorithm. ### Examples - O(n): Indicates that the execution time grows linearly with the input size. - O(n^2): Indicates that the execution time grows quadratically with the input size. - O(log n): Indicates that the execution time grows logarithmically with the input size. ## How to Determine Time Complexity 1. **Identify the dominant operations:** These are the operations that are executed most frequently in the algorithm. 2. **Count the number of times the dominant operations are executed:** Express this count as a function of the input size. 3. **Apply Big O notation:** Drop constant factors and lower-order terms to simplify the function. ### Example Consider a loop that iterates over an array of size $n$: ``` for i in range(n): # Some constant time operation ``` The dominant operation is the loop iteration, which is executed $n$ times. Therefore, the time complexity of this code snippet is O(n). ## Space Complexity Space complexity is a measure of the amount of memory space required by an algorithm to run as a function of the input size. Similar to time complexity, it is expressed using Big O notation. ### Considerations - Auxiliary space: The extra space required by the algorithm beyond the input. - Space for variables, data structures, and function call stack. By understanding time and space complexity, developers can make informed decisions about algorithm selection and optimize their code for better performance and scalability.