1 votes 1 votes for (int i = 1; i <=m; i += c) { ---do something ---} for (int i = 1; i <=n; i += c) { ---do something --- } What will the the tiem complexity of given code pseudococde? A. O (max(m,n)) B. O(min(m,n)) C. O( m+n) D. O(mn) Algorithms algorithms time-complexity + – sh!va asked Dec 4, 2016 sh!va 1.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply santhoshdevulapally commented Dec 4, 2016 reply Follow Share first loop takes o(m) time . and second one is o(n) time. both are independent and are not nested loops,so whichever takes max time that is the overall execution time. =O(max(m,n)) 1 votes 1 votes Kapil commented Dec 4, 2016 reply Follow Share Both A and C are right. 1 votes 1 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes we generally give complexity according to the inputs given to that algorithm, here the inputs are both m,n ...so both m,n defines the complexity and they must be included in the complexity expression, as there is no relationship between m and n are mentioned in the ques ... so ans is C http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/ Pavan Kumar Munnam answered Dec 4, 2016 • selected Dec 4, 2016 by vijaycs Pavan Kumar Munnam comment Share Follow See all 2 Comments See all 2 2 Comments reply vijaycs commented Dec 4, 2016 reply Follow Share option A is also correct. 1 votes 1 votes Sushant Gokhale commented Dec 5, 2016 reply Follow Share @Vijaycs. Here the most appropriate is answer (C) which be tightest bound as compared to option (A). 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes option A is right O(max(m,n)) RAJESHWAR YADAV answered Dec 4, 2016 RAJESHWAR YADAV comment Share Follow See 1 comment See all 1 1 comment reply Prashant. commented Dec 4, 2016 reply Follow Share O(m+n) = O(max(m,n)) isnt? 1 votes 1 votes Please log in or register to add a comment.