Hi, I read in the second solution that “the time complexity is O(n) since the list is traversed twice”. shouldn’t it be O(2n)? why is it O(n) while it’s traversed twice?
My name is Shahrukh Naeem. I hope everything is going well with you. Thank you for reaching out about this. I will try my best to answer your query!
Big-O notation gives you a hint on how your algorithm execution time depends on the input data. When you see that time complexity is O(n) you understand that there is a linear dependency between input and execution time. The constants are not mentioned.
By definition Ο(g(n)) is a set of functions for each of which the following statement holds: There exist such positive constants c and n0 that 0 ≤ f(n) ≤ cg(n) holds for all n ≥ n0. You see the definition is using an arbitrary constant c, if your g(n) itself has a constant that would not make any difference.
Eventually we have: O(cg(n)) = O(g(n)). In your particular case O(cn) = O(2n) = O(n). They both represent the same set of functions.
I hope that this guide is helpful. Remember that I am always available via message to help you with any difficulty you might encounter.