CODEWITHSUNDEEP
big-o
zeroflaw
zeroflaw

Reputation: 564

Big O Notation Summation confusion

I wish to use Big O Notation to convince others about code enhancement - both for efficiency and readability. But I am not sure whether i am wrong.

From Big O Notation, I understand that O(n) + O(n) = O(n) (approximate). Meaning, the constant in front is negligible.

However, taking an example, let say a for-loop

//Case 1: One For-Loop - O(n)
for(var i=0;i<n;i++)
{
   doA(i);
   doB(i);
}

For better readability, i prefer writing in this way:

//Case 2: Two For-Loop - O(n) + O(n)
function doA(){
   for(var i=0;i<n;i++){
     //do logic A
   }
}

function doB(){
   for(var i=0;i<n;i++){
      //do Logic B
   }
}

Such that, I can straightaway calling

doA();
doB();

...without the for-loop outside.

Now the problem is, i cannot convince myself, IF that for-loop actually takes 10 seconds. Then O(n) + O(n) is actually 20 seconds. How can we say that O(n) + O(n) is approximate-able to O(n)

Upvotes: 0

Views: 851

Answers (1)

zx485
zx485

Reputation: 29042

How can we say that O(n) + O(n) is approximate-able to O(n)

For your (university) concerns, there are four types of complexity:

  • logarithmical ( O(log(n)) )
  • linear ( O(n) )
  • polynomial ( O(n^k, k elemOf {1,2,3,...}) )
  • exponential ( O(n^n) )

Your question refers to the second case:

In Infinity O(n) + O(n) is O(n), because both are linear.
So you can think of it as

linear + linear = linear

Linear means that if you double the amount of input, the processing time doubles.

In the other, slower, cases the amount of processing time will be

  • n^2, n^3, ... in the case of polynomial complexity (Doubling the amount of input results in input^2, input^3 or input^4 processing time)
  • n^n (which is really big/slow) ... in the case of exponential complexity (Multiplying the amount of input by itself results in a processing time multiplied by itself, e.g. 3*3 = 9, 4*4 = 16, 5*5 = 25...).

Upvotes: 1

Related Questions