educative.io

Educative

Time complexity of solution 2 of Challege 7 of module 1 of ace the python coding interview

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 :slight_smile: