Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science Introduction to Data Structures Building a Linked List Linked Lists Operations

Time Complexity for Insertion in Different Languages

The videos state that in Python, the time complexity for Insertion on a Linked List is O(n) because of the need to search. When I look at Big O Notation cheat sheets, they state the average and worst time complexity for an insertion or deletion of a Single Linked or Doubly Linked List is O(1).

Is the time complexity expected to be different in all or most languages?

1 Answer

Steven Parker
Steven Parker
217,577 Points

Complexity is a conceptual issue, and should not differ between languages.

If you look carefully at the code comments, you'll see this: "Insertion takes O(1) time but finding node at insertion point takes O(n) time.".

My guess is that the cheat sheets you found are only considering the basic insertion time.