# Big O notation, code time complexity

does appending an element to a list through a for loop work in O(1) time or O(n) time? In addition, what is the time complexity does "".join that list into a string work in?

• Hello, welcome. A list is an abstract data structure. The time complexity depends on the particular implementation. If you are asking about a specific language or implementation of lists, you would want to try StackOverflow or another site.
– 6005
Jul 13 '20 at 13:30

It totally depends upon the particular implementation. In linked-lists which support circularity (where the first element, possibly a sentinel, links back to the last one) the task can indeed be achieved in $$O(1)$$ time, for it requires fetching a pointer to the tail of the list; on the other hand, on implementations which do not support doubly-linked elements or other fancy mechanisms, a full iteration to the back of the structure might be necessary, thus requiring $$O(n)$$ time.
On a side note, the term list refers to an ADT (Abstract Data Type), which is merely a type coupled with a set of operations and specifications. Thus, the term list does not inherently have to be linked to the pointer-based implementation; in fact, an ADT implementation such as Java ArrayList may be also realized on arrays, giving a random-access time complexity on any location (including the tail) in $$O(1)$$ time.