3 ms·

> An algorithm that takes infinite time Can you give an example of such an algorithm? My understanding of an algorithm is that it must terminate in a finite am

• gravypod 10y ago
  > My understanding of an algorithm is that it must terminate in a finite amount of time Any practical algorithm yes. Any theoretical algorithm no. This is where the will it hault questions come from. Check out Ackerman's function as a good example that we aren't sure if it will terminate. It is still extremely interesting from an algorithms analysis perspective but not from a CS (as I use it) perspective. Also I'm not specifically talking about algorithms. I'm talking about flaws in O() notation in practice. It is easy to make something look fast in theory when it is far slower in practice.
  • zodiac 10y ago
    The algorithm that computes Ackerman's function recursively (https://en.m.wikipedia.org/wiki/Ackermann_function https://en.m.wikipedia.org/wiki/Ackermann_function) always terminates in finite time