MadeEasy Test Series: Algorithms - Time Complexity

Question

PS : This question is similar to GATE2004-82, but different, so plz donot close it with duplicate Note, and help in answering

Comments

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)

---

@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) .

---

@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