0 0 votes PS : This question is similar to GATE2004-82, but different, so plz donot close it with duplicate Note, and help in answering Algorithms algorithms time-complexity made-easy-test-series + – Salazar 855 views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply hs_yadav commented Jan 31, 2018 reply Follow flag first half part of the aaray is....filled with 1's and rest n/2 part is zero...then value of count would be n/2 ...and for remaing n/2 times evry we will get otexecute f(count)....therefor total time would be N/2*(n2)=> O(n3) 0 0 replyShare MiNiPanda commented Jan 31, 2018 reply Follow flag @hs_yadav Alternate 1's and 0's can also give the same result na? Like f(1), f(2), f(3)...f(n/2) Which means 1^2 + 2^2 +... (n/2)^2 Sum of squares is of the form n*(n+1)(2n+1)/6 so it's O(n^3) . 0 0 replyShare Salazar commented Jan 31, 2018 reply Follow flag @MINIPanda , yes i think alternative 1's and 0's give same answer - O(n^3), but the answer is given as O(n) :( , i think that's wrong 1 1 replyShare Please log in or register to add a comment.
