Shivam Gupta Shivam Gupta - 2 months ago 14
C++ Question

Algorithms Analysis

what is the runtime of this function? Big O analysis

unsigned fibonacci(unsigned int n){
unsigned int rc; constant #1
unsigned int nMinus1; constant #1
unsigned int nMinus2; constant #1
if(n == 0){
rc=0;
}
else if(n==1){
rc=1;
}
else{
nMinus1=1;
nMinus2=0;
for(int i=2;i<=n;i++){
rc=nMinus1 + nMinus2;
nMinus2=nMinus1;
nMinus1=rc;
}
}
return rc;


6n + 11 does that make sense ?
O(n)

Answer

The only thing you should be looking at when performing big-O analysis is loops. That translates to powers of n. Coefficients and constants are meaningless. *Except in very specialized contexts.

When counting, always go for worst-case scenario. So you can ignore the first two if clauses -- they're constant. Focus on the loop.

Does it terminate? (Yes)
Does it call the function again or have inner loops? (No)
Does the loop depend on any arguments? (Yes)
It's O(n) — a linear function.


PS. You've likely been downvoted because this is a basic homework question. Your professor (or the book/website/whatever you've been reading) should have given you the basic information you need before asking you this question.

For more about Big-O (and related) complexity functions, check out the Plain English explanation of Big O here at SO.


PPS. Sorry, to answer your question: no, it doesn't make sense. I don't know where you got that 6 from, or the 11. (I can guess, but even if my guess is correct your reasoning is wrong.)

Hope this helps.

Comments