SD07 - Complexity 1

Question 1

What is an algorithm?

Answer 1

A process for computing a function that is guaranteed to terminate for all (finite) inputs

Question 2

What are the two most important characteristics used to compare algorithms?

Answer 2

Running time: Worst case, best case, and average case

Memory usage: Again, in the different cases

Question 3

If an algorithm performs n^2/4 operations for an input of size n, what is the average asymptotic time complexity of the algorithm?

Answer 3

n^2

Question 4

What is the average asymptotic time complexity of an algorithm?

Answer 4

The algorithm’s average case complexity as n tends towards infinity