moore's law and quadratic algorithm
- by damon
I was going thru a video (from coursera - by sedgewick) in which he argues that you cannot sustain Moore's law using a quadratic algorithm.He elaborates like this
In year 197* you build a computer of power X ,and need to count N objects.This takes M days
According to Moore's law,you have a computer of power 2X after 1.5 years.But now you have 2N objects to count.
If you use a quadratic algorithm,
In year 197*+1.5 ,it takes (4M)/2 = 2M days
4M because the algorithm is quadratic,and division by 2 because of doubling computer power.
I find this hard to understand.I tried to work thru this as below
To count N objects using comp=X , it takes M days.
-> N/X = M
After 1.5 yrs ,you need to count 2N objects using comp=2X
-> 2N/(2X) -> N/X -> M days
where do I go wrong? can someone please help me understand?
