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?
1
-
1$\begingroup$ 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. $\endgroup$– Caleb StanfordCommented Jul 13, 2020 at 13:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
For the first question, based on the fact that you're appending using a for loop it implies that you're doing it in O(n) since you'll loop at most n times where n is the current length of the list.
The time complexity for "".join() in Python is O(len(list)) since it'll have to iterate through the list once while creating the string.