Shivam Gupta Shivam Gupta - 11 months ago 63
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){
else if(n==1){
for(int i=2;i<=n;i++){
rc=nMinus1 + nMinus2;
return rc;

6n + 11 does that make sense ?

Answer Source

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.