Run Time Analysis

Question 1

What are we analysing when we do runtime notation?

Answer 1

The growth of the main function, as (for large inputs) constants do not matter

Question 2

What does “f=O(g)” represent?

Answer 2

f grows at most as fast as g

Question 3

What does “f=Ω(g)” represent?

Answer 3

f grows at least as fast as g

Question 4

What does “f=Θ(g)” represent?

Answer 4

f grows equally as fast as g

Question 5

What does “f=o(g)” represent?

Answer 5

f grows slower than g

Question 6

What does “f=ω(g)” represent?

Answer 6

f grows faster than g

Question 7

What are the two parts to a quick sort?

Answer 7

• Partition

- Recursive Sorting

Question 8

What are the steps for partitioning?

Answer 8

• Pick an element
• Rearrange so that everything to left is < the chosen element
• Therefore everything to right is > the element

Question 9

How is the sorting of the elements done after partitioning?

Answer 9

We need to look at both sides of the array, and look for two that are out of place.

Question 10

What is important about the pivot?

Answer 10

We must always know where it is, as it can move.

Question 11

How do we ensure that a quick sort is efficient?

Answer 11

We must always sort the shorter side of the array first

Question 12

What is the worst case for a Quick sort if the sides are vastly different?

Answer 12

theta(n^2)

Question 13

What is the worst case for a Quick sort if the sides are equal?

Answer 13

theta(n log n)