1

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.

Here are my two questions:

1) Would I be correct in saying that my g(n) is 5n+7 and that Θ(n) is linear because g(n) is linear?

2) Do I need to worry about upper and lower bounds even though this function has a linear runtime?

int fib(int n)
{
    int fib = 1;                                    //1
    int num1 = 0;                                   //1
    int num2 = 1;                                   //1

    for(int i = 0; i < n; i++)                      // 1 + (n+1) + 1
    {
            fib = num1 + num2;                      //2n
            num1 = num2;                            //1n
            num2= fib;                              //1n
    }
    return fib;                                     //1
}                                                   //----------------
                                                    //5n+7 <- runtime as a function of n

As far as I understand there would be no upper or lower bounds because the runtime is linear.

Chris Douglas
  • 39
  • 7
  • I'd be careful about assigning actual time values to each operation, because while an add takes only half a cycle on most modern cpu's, a read/write may take upto 80. – meowgoesthedog Jul 17 '17 at 08:18
  • Not to mention what a compiler does with this snippet and how it will look in the end. That's the reason why the O-notations is so helpful, because it abstracts away all the time-references and implementation details. You could build a custom CPU that does all the operations in one cycle. But it would still have to loop `n` times. – SkryptX Jul 17 '17 at 10:16

1 Answers1

1

1) Would I be correct in saying that my g(n) is 5n+7 and that Θ(n) is linear because g(n) is linear?

Yes, kind of. I would discourage you to ever name a certain g(n) because understand that a programming language is not a good representation of a mathematical function. You could program your function in a recursive manner and have a completely different analysis or it wouldn't even be possible in the way you did it. But what stays the same is fact that your algorithm always fulfills O(n) and proportional to Θ(g(n)) with g(n) = n.

To understand the difference between O(g(n)) and Θ(g(n)) look here: What is the difference between Θ(n) and O(n)?

2) Do I need to worry about upper and lower bounds even though this function has a linear runtime?

No you don't. Not in this algorithm. There is no better or worse case in the Fibonacci algorithm, so it will always finish with Θ(n). Note that I used Big-Theta and not the O-notation because your runtime is exactely n and not at most n.

SkryptX
  • 813
  • 1
  • 9
  • 24
  • Okay! This makes sense! `O(n)` seems like a worse case scenario kind of deal. So if I wanted to avoid sounding like a knucklehead I could say "5n+7 is of `O(n)` and also of `Θ(n)` because `O(n)` and `Θ(n)` are proportional to each other"? – Chris Douglas Jul 17 '17 at 08:44
  • I would not compare `O(n)` and `Θ(n)`. Especially `Θ(n)` does not necessarily have to exist, but if it exists, `O(n)` is equal to `Θ(n)` (unidirectional!!) because `Θ(n)` is a stronger bound than `O(n)`. I would argue that the algorithm has the same upper and lower bound of being proportional to `n` and therefore qualifies for Big-Theta `Θ(n)`. That's all. – SkryptX Jul 17 '17 at 09:03