Big O Notation and Time Complexity

These flashcards cover key concepts and terms related to Big O notation and time complexities, providing definitions to aid in understanding and memorization.

O(1)

Constant time complexity; the operation executes in a constant amount of time regardless of input size.

O(n)

Linear time complexity; execution time grows linearly with the input size.

O(n^2)

Quadratic time complexity; the execution time increases proportionally to the square of the number of inputs.

O(log n)

Logarithmic time complexity; execution time grows logarithmically as the input size increases.

Logarithm

The exponent by which a base must be raised to produce a given number.

Binary Search

An example of O(log n) time complexity; it finds an item in a sorted array by repeatedly dividing the search interval in half.

Input Size

The amount of data being processed, which can fundamentally affect the execution time of an algorithm.

Time Complexity

A measure of the amount of time an algorithm takes to complete as a function of the length of the input.

Space Complexity

A measure of the amount of working storage an algorithm needs.

Common Logarithms

Logarithms with base 10, often written simply as log.