Algorithm Efficiency and Complexity

Definitions and Basics

• 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).

Big O Notation

• 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).

Time Complexity Types

• 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

• 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.

P and NP Complexity Classes

• 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.