Computing Time T(n) and Big-O with an infinite loop

I'm confused on how to create a function T(n) to measure computing 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 am stuck trying create the function to represe开发者_运维技巧nt its computing time. I have written that its computing time is T(n) = [Summation i=0 until (n-2)] (2^j). 2^j represents the value of x with the current value of j from the inner loop. After discussing this with my peers, we definitely agree that the computing time is certainly not dependent on the value of n. We also could be completely over-thinking this as the loop is infinite and there is simply no way to express its computing time. Any help is greatly appreciated.

---

Algorithm complexity is only defined for algorithms, which by (the most often accepted) definition must terminate. This process doesn't terminate (except "in practice" as Marcelo notes; i.e. as a program on a real machine vs. in theory on a theoretical Turing machine with an infinite tape and all the time in the world) so is not an algorithm. So it has no "algorithmic time complexity".

Trying to determine the algorithmic complexity for a non-algorithm is a futile exercise, as is trying to express its running time as a polynomial if it's an infinite process.

---

The Big-O complexity of a genuinely infinite loop is undefined. Here's why:

The definition for Big O notation says that:

f(N) = O(g(N)) if and only if f(n) <= |M g(n)| for some constant M, and for all n >= n0

However, the prerequisite is that f(n) and g(n) are real-valued functions.

In the case of an infinite loop, the hypothetical value of the time taken to complete the loop is infinite. Thus the function f(n) will not map N to a Real number. Hence, f(N) is not a real-valued function, and we cannot apply the standard Big O definition in a way that makes mathematical sense.

(The Wikipedia page on Big O Notation states the definition more formally, but the outcome is the same.)

---

We would also argue that by the common definition, an algorithm that does not complete in a finite number of steps is not strictly an algorithm. (See the Wikipedia description of an algorithm for example.) Since an infinite loop doesn't complete ... ever ... it isn't an algorithm, and can't have an algorithmic complexity.

(However, I dislike this explanation since it is relying on a particular definition of the term "algorithm". The question doesn't actually use that term.)

---

Well, in the real world, you're not going to get an answer for obvious reasons, but in math... why not.

I'll write down the time equation of the function:

T(n) = n-1 * T(X) 

T(X) is the time for the inner loop. I'll expend it: X1 = initial value of 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 when 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 Natural Numbers set range, but in Integer set it's easily solved with -1 (actually any integer smaller then 0).

So, the time complexity for T(n) would be (n-1) * (-1) = 1 - n.

I don't know what's useful about this, but I hope it'll do the trick for you.