Algorithmic Complexity

• Algorithmic complexity measures the resources an algorithm needs relative to problem size.
• It is expressed with Big O notation, describing asymptotic behavior as input grows.

Time Complexity

• Time complexity refers to the amount of time an algorithm needs as a function of input size.

Space Complexity

• Space complexity refers to the amount of memory space an algorithm requires as a function of input size.

Common Complexities

• Constant complexity, denoted as O(1), means the time/space is constant, irrespective of input size, like accessing an array element.
• Logarithmic complexity, denoted as O(log N), time/space increases logarithmically with input size, like binary search.
• Linear complexity, denoted as O(N), means time/space increases linearly with input size, like looping through a list.
• Log-linear complexity, denoted as O(N log N), time/space increases log-linearly with input size, like merge sort.
• Quadratic complexity, denoted as O(N^2), time/space increases quadratically with input size, like comparing each pair of elements in a list.
• Cubic complexity, denoted as O(N^3), represents time/space increasing cubically with input size, such as matrix multiplication.
• Exponential complexity, denoted as O(2^N), means time/space increases exponentially with input size, like trying all combinations.
• Factorial complexity, denoted as O(N!), means time/space increases factorially with input size, like generating all list permutations.
• Polynomial complexity, denoted as O(N^k), the time/space increases polynomially with input size.

Example: Finding the maximum Value in an Array

• Problem: Find the maximum value in an array of n integers.
• The algorithm initializes max_value to the array's first element.
• The algorithm then iterates through the array, comparing each element to max_value.
• The algorithm updates max_value if an element is greater.
• The algorithm returns max_value after checking all elements.
• Time complexity: O(n) - Linear, because it iterates through all elements once.
• Space complexity: O(1) - Constant, only storing max_value.