0 votes 0 votes What is the time complexity of the following? for(i=0; i < n *n ; i = i *i) print("*"); Algorithms time-complexity algorithms asymptotic-notation + – smsubham asked Aug 9, 2018 smsubham 735 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply arvin commented Aug 9, 2018 reply Follow Share i think this will be infinity as value of i will always be a 0 and it will never be >n2 so the loop will run forever. if we go by another way it will run till the stack becomes full. so if we consider this way it should be O(n).. 0 votes 0 votes Ravi Dubey commented Aug 9, 2018 reply Follow Share Loop will not stop 0 votes 0 votes Siddharth Bhardawaj commented Aug 9, 2018 reply Follow Share This will go forthe infinite loop as i value always 0. So , no time complexity for this code.... 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes As i=0 initially, i=i*I gives i=0 always so, Loop will not stop Ravi Dubey answered Aug 9, 2018 Ravi Dubey comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Aug 10, 2018 reply Follow Share Wrong. Found the answer on stackoverflow, check my answer. 0 votes 0 votes Please log in or register to add a comment.
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). Abbas2131 answered Aug 9, 2018 Abbas2131 comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Aug 10, 2018 reply Follow Share Wrong. Found the answer on stackoverflow, check my answer. 0 votes 0 votes Please log in or register to add a comment.
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 smsubham answered Aug 10, 2018 smsubham comment Share Follow See all 3 Comments See all 3 3 Comments reply Abbas2131 commented Aug 10, 2018 reply Follow Share Its just a fancy way of saying that the loop will not terminate and will have infinite time period. 1 votes 1 votes nephron commented Oct 31, 2018 reply Follow Share smsubham hahahha..... in one word u could have said infinite loop instead u r calling every other's answer as incorrect. 2 votes 2 votes smsubham commented Oct 31, 2018 reply Follow Share @abbas it's asking for time complexity and I said that it's not defined, though you have somehow derived a time complexity for it. And it's not fancy way just the way it's said in computer science. @nephron yes infinite loop but it's asking for time complexity. I have given its time complexity which isn't defined for this. 0 votes 0 votes Please log in or register to add a comment.