Algorithm: Efficiency and complexity

Algorithm Efficiency and Complexity

An algorithm is a finite sequence of unambiguous instructions to solve a class of problems or perform a computation.
The efficiency of an algorithm quantifies the amount of resources, such as time and storage, necessary for its execution.
Complexity measures the rate of resource usage growth as the input size increases.
Complexity can be analysed in terms of time complexity (how the running time grows with input size) and space complexity (how the space requirements grow with input size).

The Big O notation quantifies upper bounds or worst-case scenario of an algorithm.
If an algorithm has time complexity O(n), it implies that the algorithm’s running time increases at most linearly with the input size.
Some other common time complexities include O(1) (constant time), O(log n) (logarithmic time), O(n log n) (linear-logarithmic time), O(n^2) (quadratic time), and O(2^n) (exponential time).

Constant time (O(1)): Running time of the algorithm doesn’t change with the size of the input.
Linear time (O(n)): Running time of the algorithm increases linearly with the size of input.
Quadratic time (O(n^2)): Running time of the algorithm is proportional to the square of the input.
Logarithmic time (O(log n)): Running time of the algorithm decreases with the increase in size of input.

Space complexity refers to the amount of memory an algorithm needs to run to completion.
When analysing space complexity, we consider both the fixed part (space required to store input and variables) and the variable part (dynamic memory).
Space efficiency often contrasts with time efficiency; algorithms that are extremely space-efficient might be less time-efficient, and vice versa.

The P complexity class contains problems for which an efficient (i.e., polynomial-time) algorithm exists for their solution.
The NP class contains problems for which an efficient algorithm exists to verify, but not necessarily compute, their solutions.
An important open question in computer science is the P vs NP problem, which asks whether every problem for which a solution can be checked quickly also has a solution that can be computed quickly.