SD08 - Complexity 2

Question 1

What is the ‘Big O’ notation?

Answer 1

A representation of the asymptotic time complexity of an algorithm.
It captures the most dominant term of the complexity function, typically a function of n

Question 2

What is the complexity of this function?

f(n) = 6n^3 + 4n^2 - 4n + 6

Answer 2

O(n^3)

Question 3

What is the complexity of recognising a string using a finite-state automaton?

Answer 3

O(n)

Question 4

Which of these complexities is largest?
O(n)
O(n log n)
O(log n)

Answer 4

O(n log n)

Question 5

What is the ideal complexity?

Answer 5

O(1)

Not possible for most problems though

Question 6

Does an algorithm of O(log n) always perform faster than an O(n) algorithm?

Answer 6

No, as the functions have been simplified. They only describe the algorithms behaviours as n gets suitably large.

Question 7

What is a pathological case for an algorithm?

Answer 7

A situation where the algorithm performs much worse than on average

e.g. An insertion sort with a reverse sorted list. It does twice as much work as on average