Shivam Gupta - 2 months ago 14

C++ Question

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.

Source (Stackoverflow)

Comments