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
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Apply the definitions. $\endgroup$– RaphaelCommented Apr 1, 2016 at 5:44
-
$\begingroup$ stackoverflow.com/questions/7733397/… $\endgroup$– flamingpenguinCommented Apr 1, 2016 at 10:29
-
$\begingroup$ @flamingpenguin These answers are not very strong. (As per usual when you ask about CS topics on Stack Overflow.) $\endgroup$– RaphaelCommented Apr 1, 2016 at 13:40
-
$\begingroup$ It is the sound of one hand clapping. Sorry, just joking. D.W.'s answer is correct: it's either infinite, or "there is no such time complexity". $\endgroup$– jbappleCommented Apr 19, 2016 at 1:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Another example of 'the number of steps an infinite computation takes' is "halting on a non-standard number". Interesting if you're into logical foundations, not so interesting in practice. $\endgroup$ Commented Apr 18, 2016 at 17:54
$\begingroup$
$\endgroup$
1
Basically time complexity usage makes it easy to calculate the running time of a program and this complexity is depicted in Big-O notation. But since the loop never ends it has no "algorithmic time complexity" Trying to estimate such loop's complexity would be weird and of no good use as infinity is not a real number.
-
$\begingroup$ The statement that it doesn't make much sense to try to measure the time complexity of an infinite loop is correct but that's already included in the accepted answer. Your first sentence, though, is just wrong. Time complexity doesn't make it easy or even possible to calculate the running time (in seconds or anything else) of a program, since it ignores "short" inputs and discards low-order terms and even constant factors. $\endgroup$ Commented Apr 28, 2016 at 21:02