Is the runtime of the append procedure O(n)?

Question

For example, in OCaml when you are appending an item to a list of length n.

x@[mylist]

Answer 1

Yes, the runtime of @ in OCaml is O(n) (where n is the length of the left operand).

Generally appending to the end of an immutable singly linked list (or an immutable doubly linked list for that matter) will always be O(n).

Answer 2

Your code snippet doesn't match your question, which suggests you're confused about what the operator does or which operator to use.

The @ or List.append operator concatenates 2 lists, and list1 @ list2 takes O(length(list1)) time and is not tail-recursive. rev_append is tail-recursive but still O(n) in time. The usual way to add an item to a list however is with the :: constructor, and item :: mylist takes O(1) time.

Answer 3

Yes, as mentioned, there are two reasons why it must be O(n):

1. You must iterate to the end of the singly-linked list, which takes O(n)

2. Since pairs are immutable, you must copy all the pairs in the first list in order to append, which also takes O(n)

A related interesting topic is tail-recursive vs non-tail recursive ways to append