Order of an Algorithm

Question 1

If the size of a problem is increased by some factor k then:

an algorithm of linear order will take approximately ___ times as long to complete

an algorithm of quadratic order will take approximately ___ times as long to complete

an algorithm of cubic order will take approximately ___ times as long to complete.

Answer 1

k

k^2

k^3

Question 2

Why is the answer to part (a) an estimate?

TOPIC: order of an algorithm. Use the scenario of quadratic order

Answer 2

the quadratic order does not mean the order is proportional to n^2, it could be n^2 + 2n etc. However in part (a) quadratic order is assumed to be just n^2 making our answer an estimate.

Question 3

2019 June A2 question:

For a list of n numbers the quick sort algorithm has an average order nlogn. Given that it takes 2.32 seconds to run an algorithm. When n=450.

Calculate approximately how long it will take to the nearest tenth of a second to run an algorithm when n=11250

Answer 3

run time
= 2.32 x (11250log11250 / 450log450)
= 88.6 seconds (nearest tenth)

Question 4

Order of an algorithm

Answer 4

is a measure of the efficiency as function of the size

Question 5

Size

Answer 5

the measure if its complexity (usually the number of items in the list)

Question 6

Efficiency

Answer 6

is a measure of its run time. This is proportional to the number of operations