0
$\begingroup$

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?

$\endgroup$
  • 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$ – 6005 Jul 13 at 13:30
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.