algorithms (asymptotic notation)

Question 1

constant

1st O(1)

Answer 1

• The time complexity remains the same regardless of the number of items.
• For example finding the first item in the list will always take the same amount of time regardless of the size of the list.

Question 2

Logarithmic

2nd O(log(n)

Answer 2

• Inverse of exponentiation.
• The increase in time complexity decreases as the number of items increases.
• Examples binary search and binary search tree.

Question 3

linear

3rd O(n)

Answer 3

The time complexity is proportional to the number of items. Linear search is an example of linear complexity as each item has to be evaluated.

Question 4

polynomial

4th O(n^K)

Answer 4

K is a constant value.

The rate at which time complexity rises increases as the number of items gets larger. Bubble sort is an example of this due to the nested loops.

Question 5

linearithmic

5th O(n log(n))

Answer 5

The product of linear and Logarithmic operation. The execution time grows faster than a linear function but slower than any polynomial.

Question 6

exponential

6th O(k^n)

Answer 6

The time complexity increases exponentially as the number of items gets larger. Recursive problems (Fibonacci sequence) if k = 2 the growth will double in size.

Question 7

factorial

7th O(n!)

Answer 7

The time complexity increases extremely quickly as the number gets larger. The travelling salesman is an example of this due to the only solution being a brute force search.

Question 8

tractable problem

Answer 8

A problem that is solvable by a polynomial-time algorithm
This means it can be solved in a reasonable amount of time
The upper bound (worst-case scenario) is polynomial

Question 9

intractable problem

Answer 9

A problem that cannot be solved by a polynomial-time algorithm
This means that, although an algorithm can be written to find the correct answer, it will not be solved in a reasonable amount of time
The lower bound (best-case scenario) is exponential

Question 10

Big O notation

Answer 10

-To describe how the time requirements of an algorithm grow in relation to the number of items being processed
-This allows algorithms to be compared in relation to their complexity
Independent of actual hardware
how long an algorithm takes in the worst-case scenario
-An O is used as a prefix for all expressions written in Big-O Notation
n is used to refer to the number of items