Anyone doing D1? Help needed!

Anyone out there taking the OCR D1 module this summer? If so can anyone tell me what a quadratic order algorithm is?
An example question in a paper would be: 'A shuttle sort alorithm is a quadratic order algorithm. Explain briefly what this statement means.'
This sort of question seems to come up in quite a bit in the few past papers I've looked at and I haven't got a clue how to answer it as I have no idea how to explain what a quadratic order algorithm is.
Any help?

Kathy

Reply 1

fais

I've not done D1 but a quadratic order algorithm is one that has a complexity of the order (n^2). I.e. given an input size n, the relation governing the amount of calculations required (its efficiency) is dominant on the n^2 term.

I've only ever heard of this type of complexity as polynomial but I guess quadratic is a specific subset.

Reply 2

KathyL

Thanks, that helps a little. Some of D1 is just a foreign language to me! lol. Least I can do most of it!

Reply 3

PlaystationStudies

Basically, the order of an algorithm tells you about how the time taken to solve a problem will change as the problem gets larger.

You can have linear order algorithms (to the power of 1), quadratic order algorithms (to the power of 2), cubic order algorithms (to the power of 3), exponential order algorithms (to the power of n) etc. An example of the effect they have on time taken is this:

Linear order:

If it takes 10 seconds for a linear order algorithm to solve a problem of size 100, how long does it take to solve a problem of size 400?

The increase in n is *4. The increase in t is *4. Therefore, time taken is now 40 seconds.

Quadratic order:

If it takes 10 seconds for a quadratic order algorithm to solve a problem of size 100, how long does it take to solve a problem of size 400?

The increase in n is *4. The increase in t is *4². Therefore, time taken is now 160 seconds.

Cubic order:

If it takes 10 seconds for a cubic order algorithm to solve a problem of size 100, how long does it take to solve a problem of size 400?

The increase in n is *4. The increase in t is *4³. Therefore, time taken is now 640 seconds.

Reply 4

KathyL

Thanks! That really helps! :smile:

Kathy

Reply 5

username43524

A quick question about D1,If you get given a sequence of n number of numbers, do you ever have to work out wether the order is linear, quadratic or cubic? And if so how do you do that?
cheers

Anyone ? lol

scottnoplot

A quick question about D1,If you get given a sequence of n number of numbers, do you ever have to work out wether the order is linear, quadratic or cubic? And if so how do you do that?
cheers

I'm afraid I don't understand your question. Would you like to rephrase it?

Reply 8

username43524

rnd

I'm afraid I don't understand your question. Would you like to rephrase it?

Sorry about that it wasn't worded very well was it lol.
The order of an algorithm would either be linear, quadratic, cubic or exponential. Would you ever have to work out which one of these an algorithm is, or are you just always told it if you need to know it.
I hope that's rephrased better lol, thanks.