Algorithm Running Time

A function that maps the input size to the number of elementary operations performed by the algorithm.

The worst-case running time of an algorithm is the maximum number of elementary operations that the algorithm performs over all possible inputs of a given size.

Measures the number of comparisons made between the target element (k) and list elements (xs) in the linear search algorithm.

An algorithm that iterates through each element in a list (xs) to locate a target element (k). If the target is found, it returns its index; otherwise, it returns -1.

The size of the input to an algorithm, typically measured as the number of elements, size of a list, or number of digits in a number.

Comparisons, arithmetic operations (+, -, *, /), boolean operations (&&, ||, !), assignments, and logical operations (AND, OR, NOT).

The process of focusing on the most frequent elementary operation in an algorithm, instead of considering all operations individually.

The analysis of an algorithm's running time using asymptotic notation, which describes the growth rate of the running time as the input size grows.

The maximum number of operations an algorithm performs for a given input size, considering the worst-case scenario.

The running time of an algorithm is expressed as a function of the input size.

The number of comparisons required to find an element k in a sorted list of size n is at most n. This occurs when k is not in the list or is the last element.

The algorithm computes the Cartesian product of two lists, xs and ys, by creating pairs of elements from both lists.

The worst-case running time of the Cartesian product algorithm is T(n, m) = n * m, where n is the size of xs and m is the size of ys.

For a list of size n, the binary search algorithm performs log2(n) steps. However, each step involves 5 operations: 3 comparisons and 2 assignments.

The worst-case running time of the binary search algorithm is 5 * log2(n).

A function expressed using O-notation captures the most significant term, ignoring constant factors and lower-order terms. For example, O(n) captures the linear growth of an algorithm, regardless of specific constants or additional logarithmic terms.

O-notation provides an upper bound for a function's growth. This means a function's growth will never exceed the rate specified by the O-notation.

Constant running time is independent of the input size. It takes the same amount of time for any input, like accessing a value in a hash table.

Linear running time directly scales with the input size. If you double the input, the time doubles as well. Things like iterating through a list once are linear.

Logarithmic running time increases very slowly as the input, n, grows. This means the running time grows proportionally to the logarithm of the input. The input size must increase exponentially for the running time to double. Binary search is an example of a logarithmic algorithm.

The running time of an operation can be considered to be O(mn) if the operation requires a loop that runs n times, and for each iteration of the outer loop, the code inside it requires m operations. For example, multiplying two matrices.

In O-notation, we can often ignore smaller summands. For example, an algorithm with a running time of n + logn can be approximated as O(n) because the linear term dominates for larger input sizes.

O-notation ignores constant factors. An algorithm with a running time of 5logn is considered as O(logn) because the constant factor 5 does not significantly impact the overall growth of the function.

The time it takes an algorithm to complete, expressed as a function of the input size.

A way to describe how the running time of an algorithm grows as the input size increases. Uses mathematical notation like O(n), O(n log n), etc.

An algorithm that takes a time proportional to the input size to complete (e.g., O(n)).

An algorithm whose running time grows quadratically with the input size (e.g., O(n²)).

An algorithm whose running time grows exponentially with the input size (e.g., O(2^n)).

An algorithm whose running time is bounded by a function of the input size 'n' that is considered efficient (e.g., O(n), O(n log n)).

The fastest possible time an algorithm can take to solve a problem, regardless of the specific algorithm used.

The maximum time an algorithm might take to solve a problem, considering the worst-case scenario.

The minimum number of comparisons required for any comparison-based sorting algorithm to sort a list of n elements is at least n/2. This is because each element needs to be compared at least once, and there are n elements.

A decision tree represents the execution of a comparison-based algorithm. Each internal node contains a comparison between two elements, and each edge represents the result of the comparison. The leaves of the tree represent the possible output permutations of the algorithm.

The worst-case running time of a comparison-based algorithm is at least equal to the height of its decision tree. This is because the height represents the longest path from the root to a leaf, which corresponds to the maximum number of comparisons required for a particular input.

The number of leaves in a decision tree corresponds to the number of possible output permutations of the comparison-based algorithm. This is because each leaf represents a unique sorted output configuration.

Any comparison-based sorting algorithm requires at least log(n!) comparisons in the worst case. This is because the decision tree for such an algorithm must have at least n! leaves (representing all possible permutations), and the height of the tree is at least log(n!).

The factorial function n! represents the product of all natural numbers up to n. It captures the number of ways to arrange _n distinct objects in a sequence.

The approximation log(n!) ≥ nlogn - n can be obtained by using Stirling's approximation. This inequality provides a lower bound for the logarithm of the factorial function.

The lower bound for the worst-case running time of any comparison-based sorting algorithm is Ω(nlogn). This is because log(n!) ≥ nlogn - n, and the constant factor does not affect asymptotic growth.