OK I was doing algarithms for A-level further maths, and I want to know how this works (I don't think it has that much to do with algorithms but i may be wrong). Heres a question I had involving it:
A computer takes 1.5 seconds to sort 1000 numbers. If it is a quadratic complexity, how long would it take to sort 100000 numbers?
I think it has something to do with squaring the time whenever the number of numbers, but when I attempted the question I ended up with a huge mess. Please can I have step by step instructions and information on quadratic complexities, what they are used fo etc (anything I might need to know). Thankyou.
2007-09-30 08:09:56 · 2 answers · asked by honourableone 3 in Science & Mathematics ➔ Mathematics
demiurge42, I understand your answer up untill you say that the answer is 1.5 * 10^5, when you just said it was 10^4 (which i understood how you got). Can someone verify it the answer was supposed to be 10^4? if not then I think i need more explanation please. I dont like not understanding someting I might need in an exam....
2007-09-30 08:30:56 · update #1
Ok, quadratic complexity just means that time taken is proportional to the number of elements squared.
Written out, this is t=kn², where t is time taken, n is number of elements and k is a constant of proportionality.
With the initial information, we know 1.5=k*1000², so k=1.5*10^-6 (0.0000015)
This gives us the fourmula for the time taken to sort 100000 (one hundred thousand- I assume you meant this and not a million), so t=k*n²=1.5*10^-6*100000²=1.5*10^4 seconds
2007-10-01 01:15:26 · answer #1 · answered by Anonymous · 0⤊ 0⤋
You are increasing the number of data from 1,000 to 100,000. This is 100 times as much data. Since the time it takes the algorithm to process depends on the square of the the number of data elements, this means it takes 100^2 = 10^4 times as long to process. So the total time with 100,000 is about 1.5 * 10^5 seconds.
2007-09-30 15:18:58 · answer #2 · answered by Demiurge42 7 · 1⤊ 0⤋