Further Maths, D1 - Dijkstra's Algorithm

[I-need-help]

Hi, I can do Dijkstra's Algorithm alright, but I always have problems with questions which have some relevance to the "Order of the Algorithm".

For example, in the Further Maths, Decision 1 (OCR) textbook:

8) Suppose you purchase a new computer which is 100 times as fast as your old one. What gain in problem size per hour would you achieve in the use of Dijkstra's Algorithm? Show all necessary working.

I know that the order of Dijkstra's is n² - a quadratic- and that you could use the relationship of: t α n²

Please help me!

Thank You :)

 

[willem2]

If the order of the algorithm is n^2, this means there's a constant C, such that the problem can be solved in Cn^2 steps.

Suppose that you're willing to wait a time T for the answer. The speed of your old computer is v of those steps each second, so it can do vT steps in time T, and you can do problem sizes n, such that cn^2 < vT. This means that n has to be smaller than .....

Now your new computer has speed 100v, so you can just replace v by 100 v in the condition for n you calculated before

 

[I-need-help]

@willem2 Thank you for the reply! That makes so much sense to me now. Thanks

 

[dalcde]

Do we have to know that for the D1 exam (just because I'm taking it and I didn't really expect that)?

 

[I-need-help]

Do we have to know that for the D1 exam (just because I'm taking it and I didn't really expect that)?

Hmmm, after looking at several past papers, it doesn't seem as if they would ask you anything like that. But be careful anyway, they do randomly throw related things in there.