SLR8 Classification of algorithms Flashcards
Big-O notation
“Used in computer science to describe the performance or complexity of an algorithm.”
Constant time
“O(1), if the value of T(n) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array.”
Logarithmic time
“T(n) = O(log n). An O(log n) algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.”
Linear time
“O(n). Informally, this means that for large enough input sizes, the running time increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list.”
Polynomial time
“An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(nk) for some constant k.”
Exponential time
“An algorithm is said to be exponential time if T(n) is upper bounded by 2poly(n), where poly(n) is some polynomial in n. More formally, an algorithm is exponential time if T(n) is bounded by O(2nk) for some constant k.”
Time complexity
“Quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input; this is commonly expressed using Big-O notation.”
Tractable algorithms
“A problem which can be solved by computer algorithms that run in polynomial time.”
Intractable algorithms
“No efficient algorithm exists to solve a given problem (in polynomial time or better).”
Halting problem
“The problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.”
“Used in computer science to describe the performance or complexity of an algorithm.”
Big-O notation
“O(1), if the value of T(n) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array.”
Constant time
“T(n) = O(log n). An O(log n) algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.”
Logarithmic time
“O(n). Informally, this means that for large enough input sizes, the running time increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list.”
Linear time
“An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(nk) for some constant k.”
Polynomial time
