When were are talking Time Complexity then as I have understood it. then to perform a while loop that will result in the cost of n(-1)/2 Further more the cost of a for loop is n(n+1)/2 - 1 but what is the cost of a recursive call?

  • $\begingroup$ The time complexity of recursive calls is measured the same way as iterative procedures. However the space of a recursive call is different because each "frame" in the "call stack" will take up some memory. $\endgroup$
    – Carpetfizz
    Dec 1, 2016 at 10:00
  • 1
    $\begingroup$ @Carpetfizz yes except when you are using [terminale recursion ](en.wikipedia.org/wiki/Tail_call) $\endgroup$
    – reuns
    Dec 1, 2016 at 13:02
  • $\begingroup$ @Nulle I think you didn't understand your course. For estimating the complexity you have to count how many "unit instruction" are needed for executing the algorithm. That there is a for or while loop or a recursion in your algorithm doesn't change that you have to count how many unit instructions are executed... $\endgroup$
    – reuns
    Dec 1, 2016 at 13:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.