Lower bound tells you how much it's worth to improve the SOTA. It gives you a hint that you can do better.

So it's more like polar star. Maybe not directly practical, but it will lead tons of people in the right direction.

It's a reduction from multitape Turing machine to tree evaluations. If your "real algorithm" is straightforwardly modeled by a multitape TM, then it might be possible to use this proof to reduce the space. Otherwise, I don't think so.

It does have an impact. It wont give you stackoverflow like code to copy-paste though.

Analogy is thermodynamics says how efficient a heat engine _could_ be. If your engine is way below that you know there how much of an improvement there _could_ be, that it's not an impossible problem. That will get people to build better stuff.

Upper bound on the space required. Anything, that is computable.

> Does it have any import on real algorithms?

It depends on the constants, but if the constants are good, you can have VMs for example that make memory usage smaller.

> Does it have any import on real algorithms?

As-in algorithms you'll care about if you're a programmer and not overly interested in theory? Not really, no.

I think this means that while Log grows to infinity, it does that so slowly that it can often be treated as if it were a coefficient. Coefficients are ignored in big O notation, hence the negligibly small comment.

t/log(t) is 'closer to' t than it is to sqrt(t) as t heads toward infinity.

e.g:

    4/log2(4) = 4/2 = 2
    sqrt(4) = 2

    2^32/log2(2^32) = 2^32/32 = 2^27
    sqrt(2^32) = 2^16

Maybe I'm missing context, but that sounds like O(n) or Ω(n).