Written by the Fiveable Content Team • Last updated September 2025
Verified for the 2026 exam
Verified for the 2026 exam•Written by the Fiveable Content Team • Last updated September 2025
Definition
Polynomial efficiency refers to an algorithm or function that has a time complexity that can be represented by a polynomial equation. This means that the running time of the algorithm grows at a rate proportional to some power of the input size.
Exponential efficiency refers to an algorithm or function that has a time complexity that grows exponentially with the input size. This means that as the input size increases, the running time increases at an exponential rate.
Logarithmic Efficiency: Logarithmic efficiency refers to an algorithm or function that has a time complexity that grows logarithmically with the input size. This means that as the input size increases, the running time increases at a much slower rate compared to linear or polynomial functions.
Linear Efficiency: Linear efficiency refers to an algorithm or function that has a time complexity that grows linearly with the input size. This means that as the input size increases by n elements, the running time also increases by approximately n times.