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?
Hi @jessie_Zhao
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.
Regards,
Happy Learning 