Further Maths, D1 - Dijkstra's Algorithm!

  • #1
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 n2 - a quadratic- and that you could use the relationship of: t α n2

Please help me!

Thank You :)
 

Answers and Replies

  • #2
1,991
270
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
 
  • #3
@willem2 Thank you for the reply! That makes so much sense to me now. Thanks
 
  • #4
166
0
Do we have to know that for the D1 exam (just because I'm taking it and I didn't really expect that)?
 
  • #5
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.
 

Related Threads on Further Maths, D1 - Dijkstra's Algorithm!

  • Last Post
Replies
1
Views
2K
Replies
2
Views
712
Replies
4
Views
2K
  • Last Post
Replies
13
Views
4K
Replies
3
Views
797
  • Last Post
Replies
14
Views
7K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
1K
  • Last Post
Replies
1
Views
4K
  • Last Post
3
Replies
52
Views
9K
Top