• 0 Posts
  • 29 Comments
Joined 1 year ago
cake
Cake day: June 10th, 2023

help-circle



















  • Well landau notation only describes the behaviour as an input value tends to infinty, so yes, every real machine with constant finite memory will complete everything in constant time or loop forever, as it can only be in a finite amount of states.

    Luckily, even if our computation models (RAM/TM/…) assume infinite memory, for most algorithms the asymptotic behaviour is describing small-case behaviour quite well.

    But not always, e.g. InsertionSort is an O(n^2) algorithm, but IRL much faster than O(n log n) QuickSort/MergeSort, for n up to 7 or so. This is why in actual programs hybrid algorithms are used.