2 votes 2 votes shouldn't the answer be O(n^3)? Algorithms made-easy-test-series algorithms time-complexity + – Kalpataru Bose asked Dec 31, 2017 • edited Mar 5, 2019 by Aditi Singh Kalpataru Bose 642 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Anu007 commented Dec 31, 2017 reply Follow Share it will be O(n2) 0 votes 0 votes Kalpataru Bose commented Dec 31, 2017 reply Follow Share How? 0 votes 0 votes Ashwin Kulkarni commented Jan 1, 2018 reply Follow Share for higher values it will give O(n2 ) , we should look that only while calculating these questions. 0 votes 0 votes Kalpataru Bose commented Jan 1, 2018 reply Follow Share The answer is given as O(n) 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes May be the answer given is wrong !! It should be O(n^2) as the best you can do is go for the ELSE part.. where u can clearly see that we will run a O(n) loop n times.. making the total complexity O(n^2) VAIBHAV KAUSHIK answered Jan 1, 2018 • selected Jan 9, 2018 by Kalpataru Bose VAIBHAV KAUSHIK comment Share Follow See all 3 Comments See all 3 3 Comments reply Sona Barman commented Jan 7, 2018 reply Follow Share Why we should consider only else part? 0 votes 0 votes VAIBHAV KAUSHIK commented Jan 8, 2018 reply Follow Share the else part should be considered because we are being asked about the best case... why will i run a O(n^2) loop if want a best case ?? given that i have the option of executing a O(n) loop.. 1 votes 1 votes Sona Barman commented Jan 8, 2018 reply Follow Share Thank you. 0 votes 0 votes Please log in or register to add a comment.