Algorithm: Efficiency and complexity

Algorithm: Efficiency and complexity

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.