Computation time T (n) and Big-O with infinite loop
I am confused about how to create a function T (n) to measure the computation time for a nested infinite loop. Here is the code:
x=1;
for(int i = 0;i<n-1;i++){
for(int j = 1; j<=x; j++){
cout << j << endl;
x*=2;
}
}
So the inner loop will go on forever and I get stuck trying to create a function to represent my computation time. I wrote that its computational time is T (n) = [Summing i = 0 to (n-2)] (2 ^ j). 2 ^ j represents the value x with the current value j from the inner loop. After discussing this with our peers, we definitely agree that the computational time is, of course, independent of the value of n. We could also completely rethink this, since the loop is infinite and it is simply impossible to express your computational time. Any help is appreciated.
source to share
The complexity of an algorithm is determined only for algorithms that, by the (most commonly accepted) definition, must end. This process does not end (except "in practice" as Marcelo points out, i.e., like a program on a real machine or theoretically on a theoretical Turing machine with an infinite tape and all the time in the world), so it is not an algorithm. it has no "algorithmic time complexity".
Trying to determine algorithmic complexity for a non-algorithm is a useless exercise, as it tries to express its running time as a polynomial if it is an infinite process.
source to share
The Big-O complexity of a truly infinite loop is undefined . That's why:
The definition of Big O notation states that:
f(N) = O(g(N))
if and only iff(n) <= |M g(n)|
for some constantM
and for alln >= n0
However, a prerequisite is that f(n)
and g(n)
are functions of a subset of real numbers.
In the case of an infinite loop, the value f(n)
is "infinity", which is not a Real number. Hence, we cannot apply Big O annotation to a problem (truly infinite loop) in a way that makes mathematical sense.
(The Wikipedia page on Big O Notation states this more formally.)
source to share
Well, in the real world, you won't get an answer for obvious reasons, but math ... why not.
I'll write the equation for the time of the function:
T(n) = n-1 * T(X)
T(X)
- time for the inner loop. I'll spend it: X1
= initial value x
(in this case 1
)
T(X) = T(X1 * 2) + 1 = T(X1 * 4) + 2 = ... = T(X1 * 2^j) + j
The end condition of this loop is j >= X1 * 2^j + 1
, so we want to solve:
j >= X1 * 2^j -> j = 2^j -> j <= log2(j).
The above equation has no solution in this set of natural numbers, but in Integer it is easy to solve with -1
(virtually any integer less than 0
).
So, the time complexity for T(n)
will be (n-1) * (-1) = 1 - n
.
I don't know what is helpful about this, but I hope it helps you.
source to share