0

What I've understood about time complexity is that it measures the no. of operations performed with respect to input. For example

code{

 for(int i=0;i<n;i++){     // n opertions
  print(array[i]);
 }

 for(int i=0;i<n;i++{      // n operations
  print(array[i}
 }
}

If each loop performs n operations then the total no. of operations performed will be 2n Right? Why not include that in the Time Complexity? I mean why is 2 neglected in O(n) instead of O(2n)

If n=5 then the first for loop will perform 5 operation and second will perform 5 , So totally it'll perform 10 operations. If n=10 then first loop will perform 10 and second loop will perform 10 operations , So totally the it'll perform 20 operations which is 2n. The above no. of operations will not change no matter how slow your computer performs the no.of operations performed will be 2n. Then my question is why O(n) instead of O(2n).

ks1322
  • 33,961
  • 14
  • 109
  • 164
ALLAN
  • 71
  • 6
  • O(n) = O(2n). Constants cancel. – phipsgabler Aug 12 '20 at 08:32
  • It's basically because big O is about how things scale with increasing input size – klutt Aug 12 '20 at 08:35
  • Thanks for the answer. I don't really get the real meaning of scale @klutt – ALLAN Aug 12 '20 at 08:38
  • What Big O answers is "If I double the input size, how much longer will it take?" – klutt Aug 12 '20 at 08:39
  • What Big O does NOT answer is "How long will it take for a certain input size?" – klutt Aug 12 '20 at 08:40
  • Thanks @klutt but it's too confusing or hard for my brain to get it. – ALLAN Aug 12 '20 at 08:47
  • @ALLAN Usually, those differences you're talking about are only relevant to actual implementations and not for the algorithms as a theoretical concept. When it comes to reality, there's only one way to find out what's best, and that's performance measurement for real data. – klutt Aug 12 '20 at 10:02
  • @klutt Yep, that's what i'm asking klutt. So If i'm gonna analyze a program which contains two same for loops then we'll take that constant 2 in consideration right? – ALLAN Aug 13 '20 at 15:46
  • @ALLAN You're looking for a simple yes or no answer to a complicated question. You will not find it. It all depends on what you want to do with the analysis. Sometimes it's relevant and sometimes not. But no, the 2 in 2n is actually very rarely relevant. In those situations it is relevant is basically when you are trying to do a quick optimization, but in those situations, the only important matter is actual speed. – klutt Aug 13 '20 at 23:09

0 Answers0