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.
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.