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