1 votes 1 votes main() { int (b=1;b<=n;b*=2) { for(i=0;i<b;i++) { for(j=0;j<n;j+=2) { sum+=j; } for(j=0;j<n;j*=2) { sum*=j; } } } what is the complexity? } Algorithms time-complexity algorithms asymptotic-notation + – Aboveallplayer asked Jan 29, 2017 Aboveallplayer 1.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Gate Mission 1 commented Jan 29, 2017 reply Follow Share O(n2) ? 0 votes 0 votes Aboveallplayer commented Jan 29, 2017 reply Follow Share ya how? 0 votes 0 votes Gate Mission 1 commented Jan 29, 2017 reply Follow Share //C1 for(j=0;j<n;j+=2){ sum+=j; } //C2 for(j=0;j<n;j*=2){ sum*=j; } C1 code runs O(n/2) or O(n) and C2 code runs O(logn) --> As these are innermost codes so main contribution to time complexity is of C1 code i.e O(n). Now situation is : int (b=1;b<=n;b*=2){ for(i=0;i<b;i++){ //C1 running O(n) } } B values go like 1,2,4,8,16,32,...................,2k(say) after which loop breaks, inner i loop runs 1,2,4,8,16,....2k times respectively for b values. So time complexity is (1+2+4..........+2k )(n [due to C1 code running in i loop] ) --> Now it can be solved !! 4 votes 4 votes dd commented Jan 30, 2017 reply Follow Share this is cbt2 QS ..:) I have solved it in exam btw.. adding solution. 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes @Gate Mission 1 is right. dd answered Jan 30, 2017 dd comment Share Follow See all 0 reply Please log in or register to add a comment.