Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Further Maths, D1 - Dijkstra's Algorithm!

  1. Oct 28, 2011 #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 :)
  2. jcsd
  3. Nov 24, 2011 #2
    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
  4. Nov 24, 2011 #3
    @willem2 Thank you for the reply! That makes so much sense to me now. Thanks
  5. Dec 31, 2011 #4
    Do we have to know that for the D1 exam (just because I'm taking it and I didn't really expect that)?
  6. Jan 2, 2012 #5
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook