title: Big Theta notation and time complexity of a loop
body: <p>I was told to make a loop based function that returns the nth Fibonacci number. I've already made the function and will include it down below. My assignment says to "argue that the running time of the function is Θ(n), i.e. the function is linear in n." In the books I've read and videos I've watched, Big-Theta has always been written as Θ(g(n)) and expressed as some inequality. The instructor refuses to answer any questions about this until we turn it in.</p>
  
  <p>Here are my two questions:</p>
  
  <p>1) Would I be correct in saying that my g(n) is 5n+7 and that Θ(n) is linear because g(n) is linear?</p>
  
  <p>2) Do I need to worry about upper and lower bounds even though this function has a linear runtime?</p>
  
  <pre><code>int fib(int n)
  {
      int fib = 1;                                    //1
      int num1 = 0;                                   //1
      int num2 = 1;                                   //1
  
      for(int i = 0; i &lt; n; i++)                      // 1 + (n+1) + 1
      {
              fib = num1 + num2;                      //2n
              num1 = num2;                            //1n
              num2= fib;                              //1n
      }
      return fib;                                     //1
  }                                                   //----------------
                                                      //5n+7 &lt;- runtime as a function of n
  </code></pre>
  
  <p>As far as I understand there would be no upper or lower bounds because the runtime is linear.</p>