0 votes 0 votes What is the time complexity of the following function: function(n) { for(i = 0; i < n; i = i*2) { for(j = 0; j < i; j++) { printf("*"); } } } Algorithms algorithms time-complexity + – GateAspirant999 asked May 11, 2016 • retagged Jul 7, 2022 by Lakshman Bhaiya GateAspirant999 1.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply rajan commented May 12, 2016 reply Follow Share i think zero times ??? 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes Value of i always remains 0 hence it gets trapped in outer loop indefinitely, irrespective of the values of n. That means, it doesn't depend on the input. Therefore, it's time complexity is O(1). Shyam Singh 1 answered May 12, 2016 • selected May 12, 2016 by srestha Shyam Singh 1 comment Share Follow See all 3 Comments See all 3 3 Comments reply sethi commented May 13, 2016 reply Follow Share function(n) { for(i = 1; i < n; i = i*2) { for(j = 0; j < i; j++) { printf("*"); } } } what will be the time complexity? 0 votes 0 votes Shyam Singh 1 commented May 13, 2016 reply Follow Share O(n) Values of i will be power of 2, and the inner loop will run power of 2 times. T(n) = $2^{0} + 2^{1} + ... + 2^{k}$ , where k = $\log n$ (base 2) since it is a geometric series T(n) = $2^{k+1} - 1$ T(n) = 2.n - 1 T(n) = O(n) 0 votes 0 votes Sajid Ali commented Jun 27, 2018 reply Follow Share O(n) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes if i=0 is replaced by 1 then inner loop will execute 1,2,4,8,16,32 ...log2n times so total no of times =2^logn-1/2-1=>O(2^log n)=>0(n ) Sanjay Sharma answered May 12, 2016 • edited May 12, 2016 by Sanjay Sharma Sanjay Sharma comment Share Follow See all 2 Comments See all 2 2 Comments reply cse23 commented May 12, 2016 reply Follow Share i is getting multiplied by 2 and initially i is 0 so each time it will be 0 only and j<i will not be true. so printf will not execute once also. 0 votes 0 votes Sanjay Sharma commented May 12, 2016 reply Follow Share oh yes then it seems to be incorrect or tricky question 0 votes 0 votes Please log in or register to add a comment.