comp 2 num 2

Question 1

What is an algorithm?

Answer 1

Step by step instructions to solve a problem.

Question 2

What is O(1)?

Answer 2

constant time complexity, Time requirements do not change as the size of the input increases.

Question 3

What is O(n)?

Answer 3

linear time complexity, Time requirements increase in direct proportion to the size of the input.

Question 4

What is O(n^2)?

Answer 4

quadratic time complexity, Time requirements increase in proportion to the size of the input squared.

Question 5

What is O(n^k)?

Answer 5

polynomial time complexity

Question 6

What is O(k^n)?

Answer 6

exponential time complexity, A small increase in the size of the input results in a disproportionate exponentially large increase in the time requirements.

Question 7

What is O(logn)?

Answer 7

logarithmic time complexity, As the size of the input increases, the time requirements increase at a decreasing rate.

Question 8

What is the best to worst order for these?

Answer 8

1
logn
n
nlogn
n^2
n^k
k^n

Question 9

What is always the best case time for a search algorithm?

Answer 9

o(1)

Question 10

What is the worst case time complexity for each search/sort alg?

Answer 10

linear search n
binary search logn
bubble sort n^2
insertion sort n^2
merge sort nlogn
quick sort nlogn

Question 11

Why is a merge sort nlogn?

Answer 11

Splitting array recursively until all arrays are of length 1 is logn.
Combining these n number of sublists results in multiplying by n to result in nlogn.

Question 12

What is the purpose of big o?

Answer 12

Evaluating the complexity of an algorithm in relation to space and time requirements and how they scale as the input size increases.