0

sorry if this question turns out to be very stupid, but I'm trying to get my head around the whole concept.

Lets suppose we have the following:

for(int i = 0; i < n; i++) {

      if ( ... ) { ... }
      if ( ... ) { ... }
      if ( ... ) { ... }
      if ( ... ) { ... }

}

What is its time complexity, and why?

I thought it was O(n ^ O(4) )?

James
  • 267
  • 3
  • 5
  • 14
  • 2
    It is not O(n^(O4)) it is O(n).The time complexity for if bloack comparison and assignment operations are negligible.So they are neglected – Debabrata Sep 15 '17 at 10:16
  • but what confuses me is why doesnt the if taken into consideration? It is stil an operation after all @Debabrata – James Sep 15 '17 at 10:22
  • 1
    This post should help. https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation I think you should consider the if block, then you will have O(4n), then by some math you can say the time complexity is O(n). – Petar Petrovic Sep 15 '17 at 10:33
  • 1
    If `...` can be anything, the algorithm can have a time complexity of anywhere from O(n) to O(n^n) or more. O(n ^ O(4)) doesn't make much sense syntactically though, you probably meant O(n^4), which it's most definitely not if each if-statement is constant time (in which case it's more like O(4n) = O(n)). – Bernhard Barker Sep 15 '17 at 10:39
  • 1
    If the if block does not run in constant time, then you may have another result – Petar Petrovic Sep 15 '17 at 10:39
  • 1
    @James We ignore the leading term’s constant coefficient(here in O(4n) 4 in the coefficient of leading term n), since constant factors are less significant than the rate of growth in determining computational efficiency for large inputs – Debabrata Sep 15 '17 at 10:45
  • @Dukeling I see. thank you guys for clearing the confusion. – James Sep 15 '17 at 10:53

0 Answers0