This is a poor quality article. The premise of the article is:
“Today I’ve read on Twitter a half-joke saying that basically we can just implement our code and then wait for faster computers to improve the speed of our programs. As many might now, that’s not actually the case”
It turns out this is true, because the free lunch is over. Our software will only continue to get faster if it can benefit from increased parallelism at this point. However, the argument that he makes is that because there are problems that are different time complexities, anything that has a worse time complexity of O(n) will not get linearly faster with faster processors. This is false. If you have a problem which takes X machine instructions to solve, and a new processor can execute X machine instructions N times faster, the problem will be solved N times faster. Time complexity doesn’t enter into the equation.
The author comes to the conclusion that just because your processor is faster, you can’t necessarily solve problems which are harder (where you increase the number of items in your problem), which is correct, but he tries to use this to solve a different problem, which is whether faster processors will make your software faster.
Well yes, it’s pretty obvious that for the same N, a faster CPU will “solve” the problem faster, isn’t it?
Perhaps I didn’t express myself correctly, but the point I was trying to make is that the gains you’ll get with faster hardware aren’t that much if you have a poor algorithm. Point that is made by Alfred Aho et al, not me.
Will a poor algorithm run faster with faster hardware, yes.
Right–that point is wrong. If the size of your problem increases, then you will have a problem. However, if you are solving the same problem, then the time complexity of your problem doesn’t matter at all because the amount of computation you have to do is fixed.
Article doesn’t really add much to the discussion, IMO.
It might not add much to people knowledgeable as you, but I’m pretty sure people out there could benefit from this. I’ve seen many a case of teams waiting for new hardware when in fact they have a very poor implementations of certain algorithms.
I’d be surprised if those people were reading your blog.