0

Is this O(n) or O(1)?

Version: 5, id: 6114603: the worst-case time complexity of adding to a singly-linked list after the 10th node with a size of at least 10?

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
ap0808
  • 1
  • 1
  • 1
    Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Welbog Jul 12 '21 at 22:55

2 Answers2

1

[What is] the worst-case time complexity of adding to a singly-linked list after the tenth node with a size of at least ten.

That specific task, adding an item immediately after node ten, is O(1)(a).

That's because the time taken to do it is not affected by the list size at all. It takes the exact same time whether the list has ten nodes, or a hundred billion nodes, and could be implemented as per the following pseudo-code:

def insert_after_tenth(first, item):
    tenth = first.next.next.next.next.next.next.next.next.next # O(1)
    item.next = tenth.next                                     # O(1)
    tenth.next = item                                          # O(1)

I've calculated the tenth variable in that way (rather than a loop) to make it clear that the time cost is not dependent on the list size. And, since every line is O(1), the complete operation is also O(1).

(a) Admittedly, that's based on a certain reading of the question, inserting the new item immediately after node ten. There is another reading you could argue, that of inserting at some point after node ten.

However, if that were the case, all that extra stuff about node ten would be irrelevant, since it would be O(n) regardless of where you wanted to insert.

If you wanted extra marks (assuming this is some form of classwork), you may want to mention both possibilities but the first is by far the most likely.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Since it is asking for the worst-case time complexity, Shouldn't we consider the case where we add the node to last? (no tail pointer) – ap0808 Jul 12 '21 at 23:05
  • @ap0808: that wouldn't matter. Even if there was more work involved, that work would still be independent of the list size. Hence still `O(1)`. In any case, there probably isn't any more work involved (unless there *was* a tail pointer that needed updating). For a ten-node list, the tenth node would point to `null` and the pseudo-code in my answer (added recently) would still work. – paxdiablo Jul 13 '21 at 01:24
-1

If a LinkedList has n node, where n > 10, then the worst-case time complexity is O(N) since it needs to iterate through the list to get the last Node.

user16435231
  • 1
  • While that's true for the general case of linked list processing, this *specific* case is O(1), as the number of nodes you need to iterate over is a constant ten. Hence it's not related to the size of the list. – paxdiablo Jul 15 '21 at 00:03