Expected time is just the average, expected, running time of the algorithm using the intended input.
Say you've got some few million user records and want to sort them, you might want to use an algorithm which is the most suitable for your input, and as such gives the best expected running time, as opposed to an algorithm which has better worst-case running time but worse expected running time.
Sometimes for example the constant factors for the time-complexity of an algorithm are so high that it makes sense to use algorithms with worse time-complexity but smaller constant factors, as it gives you better expected running time with small input, even though it would get horribly outperformed with bigger input.
Perhaps a better example would be the classic quicksort algorithm, which has worst-case running time of O(n²) but expected average running time of O(n log n), regardless of input. This is because the algorithm uses(or rather, may use, depending on the implementation) randomization. So it's a so-called randomized algorithm. It runs a bit differently with every invocation even with the same input. As such, thre's no universal worst-case input for the implementation, because the worst-case input depends on the way the algorithm chooses the pivot for dividing the given input. And as such, one can't just supply some pre-defined input causing the worst-case running time. This is often the case with randomized algorithms, which aim for better expected, average running time regardless of the input.
It's all about using the right algorithm for the input at hand.
Why don't we just use a different algorithm based on the size of the input?
We do. Hybrid algorithms are used all the time.
Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?
That is quite literally how most real-world implementations of sorting algorithms look like.
E.g. quick sort has quite a high overhead, so every real-world quick sort implementation switches to insertion sort for the simple cases at the lower levels of the recursion tree. Instead of switching algorithms at the leaves of the recursion, you can also simply stop sorting altogether at some pre-defined partition size, and then run insertion sort once on the "almost-sorted" result of the "aborted quick sort". This may be more efficient, because instead of having many tiny insertion sorts, you have one longer one, so you don't constantly switch between quick sort and insertion sort in the instruction cache.
Merge sort is also often combined with insertion sort. For example, for cache efficiency, you might want to switch to an in-place insertion sort as soon as the partitions are small enough to fully fit into the cache.
One of the most-widely used sorting algorithms is Timsort, which was implemented for CPython in 2002 by Tim Peters, and has since been adopted by (among others) Oracle JRE (and many others, e.g. IBM J9) as Arrays.sort
for reference types, Android, V8, Swift, and GNU Octave. It is a hybrid insertion sort and merge sort, It tries to find "runs" of already sorted elements and merges those; if it can't find any runs, it will create them by partially sorting the list with insertion sort.
Considering that it is used in some of the most widely-used implementations of some of the most widely-used languages, i.e. in Android and Swift (in other words, on pretty much every smartphone and tablet) and also in Java (in other words on pretty much every desktop and a large number of servers) and V8 (i.e. in Chrome and Node.js) and CPython, we can quite confidently say that there is probably not a single person on the planet who has not used it in some form. I don't know about you, but I wouldn't call that "not done in practice", in fact, it doesn't get any more practical than running on almost every computer in the world.
it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm)
Introsort solves this by being, as the name implies, introspective. It starts off as a quick sort, but it watches itself while it executes, and when the recursion exceeds a certain depth, it switches to heap sort. Regardless of whether it switches to heap sort in between or stays at quick sort, for very small arrays, it then switches to insertion sort.
Introsort is used in several C and C++ standard library implementations, in .NET, and with Shellsort instead of insertion sort as the final algorithm in Go.
As we have seen above, Timsort has a really clever take on this problem: if the input data doesn't fit its assumptions, it simply makes it fit by partially sorting it first!
Best Answer
Since Hashlife runs the Game of Life which is Turing complete, it can run any Turing-computable program. If the complexity for all programs run through Hashlife would be reduced by log(n), that would for example get the (NP-complete) SAT problem (where the best known implementations have O(2^n)) run in O(n). Maybe with multiple Hashlife simulations nested in each other, you could maybe solve every problem in O(log(n)). That could eventually lead to a proof for P=NP.
The problem is that the O(log(n)) only works for the average case, while the worst case still has O(n). Hashlife has three major optimisations:
Both of the latter only work so well because most configurations have many reoccuring patterns and comparatively few different possible nodes. For some of the more complex starting patterns, the Golly simulator starts with the usual very quickly growing speed (when the pattern is still small and regular), but gets slower the more the pattern grows, so it has apparently not purely logarithmic complexity.
You can use memoisation to speed up any other repeated deterministic procedure. You can use trees for efficient data management. You can use canonicalisation for immutable objects to save a lot of memory and calculations.