1 votes 1 votes What is the time complexity of the following function foo() void foo() { int i, j; for(i = 1; i <= n ; i++) for(j = i; j <= log(i); j++) printf(“gate”); } what is the time complexity? the answer given is nlogn. but I think it should be O(n) Algorithms algorithms time-complexity + – Akriti sood asked Jan 23, 2017 edited Jun 28, 2022 by makhdoom ghaya Akriti sood 1.3k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply dd commented Jan 24, 2017 reply Follow Share yes, in the given code, it should be O(n). But there is a typo in j = i. If instead j = 1, then answer would have been nlogn 0 votes 0 votes Akriti sood commented Jan 24, 2017 reply Follow Share thanks for confirming:-) 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes It should be nlogn only. When the value of i is 1-----runs for log1 times When I is 2 log 2 times When i is 3 log 3 times . . When i is n log n times So total times it runs is log1 + log 2+log 3+...logn =logn!= nLogn manish.anand answered Apr 6, 2018 manish.anand comment Share Follow See 1 comment See all 1 1 comment reply SaurabhKatkar commented Dec 24, 2019 reply Follow Share for i=1 how 1<=log(1) ?? the condition will be false it won't execute even once 0 votes 0 votes Please log in or register to add a comment.