I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs.
I just wondered that how to calculate time complexity of non terminating loops such as infinite loops
|
|
|||||
|
|
You question is really interesting. It never occur to me to find out about this. Complexities are finite. Computation is both finite and infinite. Complexity always works over the input. And number of steps are the complexity Logically, it seems to be right but technically there's nothing like an infinite complexity. You can relate this with halting problem of Turing machine. |
|||||
|
|
If the program runs forever, its running time is infinite. So, if it always enters an infinite loop, its running time is infinite. This is a degenerate case. Normally we focus only on algorithms that are certain to terminate (but see footnote). See also How to come up with the runtime of algorithms? and Is there a system behind the magic of algorithm analysis?. Footnote: When studying randomized algorithms, this gets relaxed a bit, and we frequently look at algorithms that in principle could run forever if they keep getting an unlucky choice of random bits, but whose expected running time is finite. However, if you're just starting with algorithms, it's likely that you are dealing with deterministic algorithms, not randomized algorithms, so this is unlikely to come up. |
||||
|
|
|
Your question is pretty interesting.. Logically speaking, the time complexity depends upon the input and the loops. So if it is an infinite loop, the time is also infinite. But technically, there is no infinite time complexity thing.. |
|||
|
|
