When studying O() we always end up with terms like O(N), O(N^2), O(N^3) even tho

Question

When studying O() we always end up with terms like O(N), O(N^2), O(N^3) even though there are other statements in the code that make up the overall efficiency of the program. For instance take the code below

for(i = 0; i < x; i++)

{

for(z = 0; z < x; z++)

{

          Val *= 2;

          Tmp += 1;

}

}

while(x != 0)

{   

     Val –= x;

     x--;

}

Return 0;

Would become O(2n^2 + 2n + 1). Why does it make sense to drop all of the other numbers and just take the highest-powered term? In this case O(n^2).

Explanation / Answer

According to the big O notation f(n) <= kf(n)+c where k is some constant and c is also some constant,hence in this case the O(n)=f(n) .

In the question O(2n^2+2n+1) : This is basically the function of n^2 as other terms like 2,1 are constant and n is smaller than n^2 hence the upper bound will be n^2.

Therefore,the final complexity would be O(n^2).

Note:Please do ask in case of any doubt,Thanks!!

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.