# SLR8 Classification of algorithms Flashcards

1
Q

﻿Big-O notation

A

“Used in computer science to describe the performance or complexity of an algorithm.”

2
Q

Constant time

A

“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.”

3
Q

Logarithmic time

A

“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.”

4
Q

Linear time

A

“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.”

5
Q

Polynomial time

A

“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.”

6
Q

Exponential time

A

“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.”

7
Q

Time complexity

A

“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.”

8
Q

Tractable algorithms

A

“A problem which can be solved by computer algorithms that run in polynomial time.”

9
Q

Intractable algorithms

A

“No efficient algorithm exists to solve a given problem (in polynomial time or better).”

10
Q

Halting problem

A

“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.”

11
Q

“Used in computer science to describe the performance or complexity of an algorithm.”

A

Big-O notation

12
Q

“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.”

A

Constant time

13
Q

“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.”

A

Logarithmic time

14
Q

“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.”

A

Linear time

15
Q

“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.”

A

Polynomial time

16
Q

“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.”

A

Exponential time

17
Q

“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.”

A

Time complexity

18
Q

“A problem which can be solved by computer algorithms that run in polynomial time.”

A

Tractable algorithms

19
Q

“No efficient algorithm exists to solve a given problem (in polynomial time or better).”

A

Intractable algorithms

20
Q

“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.”

A

Halting problem