title: Recurrence Relation of function with a Loop
body: <p>I have been trying to find recurrence relation that represents the runtime of the following function. I know how to solve recurrence relations and functions without loop but I have 0 clue about the following function </p>
  
  <pre><code>function derp(n):
      if n == 0
        return 1
      sum = 0
      for i = 1 to 3
         sum = sum + derp(n-1)
      return sum
  </code></pre>