I'm analyzing a piece of code that has a recursive call inside a for loop such as:

def fun(n):
    for i in range(0, 256):
         if ( n > 0):

(I only included a general piece of code not the actual version)

It is my understanding that a recursive call gets assigned T(n) = T(n-8) but what happens when it is nested inside a for loop?

  • $\begingroup$ Don't guess! Figure out what the equations stand for. $\endgroup$ – Yuval Filmus Feb 4 '18 at 20:41
  • $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Feb 4 '18 at 22:17
  • $\begingroup$ Moderator note: I removed some comments that seemed a) subsumed by OmG's answer or b) discussions about misunderstandings. $\endgroup$ – Raphael Feb 4 '18 at 22:19

As there is a loop over $F(n-8)$, so we will have 256 times $F(n-8)$. Hence, time complexity would be: $$T(n) = 256\times T(n-8) = 256\times(256\times T(n-16)) = \Theta(256^\frac{n}{8})$$.

As mentioned in comment $256 = 2^8$, we will have $T(n) = \Theta(2^n)$.

  • 1
    $\begingroup$ Note that $256^{1/8} = 2$. $\endgroup$ – Yuval Filmus Feb 4 '18 at 21:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.