Comment by voxl

Comment by voxl a day ago

2 replies

I'm not sure if you're just choosing intentionally obtuse verbiage or if you're actually saying something completely incoherent.

"Overall Complexity" is a meaningless term without you defining it. I suppose you mean that there is some lower bound limit to the amount of work relative to a model of computation, but this is a trivial statement, because the limit is always at least no work.

We have many problems where we don't know the least upper bound, so even an interesting formulation of your idea is not necessarily true: work need not be conserved at the least upper bound, because reaching the bound may not be possible and epsilon improvement might always be possible.

Finally, algorithmic complexity is the wrong analogy for reverse mathematics anyway.

zkmon a day ago

To give an example, we consider that binary search requires less work than a linear search. But there are costs and usecase considerations involved. Insertion of new recod need to use binary search to keep the data sorted. Also if the number of lookups is far less than number of records, the overall cost is more than appending and linear search. That's what I mean by by moving the complexity around.

A problem scenario doesn't have absolute characteristics. It's relative to your way of looking at it, and your definition of a problem.

  • short_sells_poo a day ago

    You are right, but this doesn't mean that the amount of work is conserved as your original message implies. The correct statement would be that "algorithmic complexity is just one aspect of actual practical complexity and an algorithm with better algorithmic complexity can end up performing worse in reality due to practical considerations of the data and the processor doing the computations".