735 views
0 votes
0 votes
What is the time complexity of the following?

for(i=0; i < n *n ; i = i *i)

print("*");

3 Answers

1 votes
1 votes
As i=0 initially, i=i*I gives i=0 always so, Loop will not stop
1 votes
1 votes

Technically it will be infinity, if i=0 or i=1 initially.
but if i>=2 intitially then O(log n2 ) = O(2log n)= O(log n).

0 votes
0 votes

This will result in infinite loop as i value will always be zero.

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.

Source: https://stackoverflow.com/questions/7733397/computing-time-tn-and-big-o-with-an-infinite-loop

No related questions found