Is the execution time of adding O (n)?

Question

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

x@ [mylist] 

Answer 1

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

Usually adding to the end of an immutable single list (or an immutable double-linked list) will always be O(n) .

Answer 2

Your piece of code does not correspond to your question, which means that you are confused by what the operator is doing or which operator to use.

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

Answer 3

Yes, as already mentioned, there are two reasons why this should be O (n):

• You have to iterate to the end of a singly linked list that takes O (n)

• Since the pairs are immutable, you must copy all the pairs in the first list to add, which also accepts O (n)

An interesting topic related to this is the tail-recursive or irregular path to add

Answer 4

In general, yes.

To illustrate, a simple (non-tail recursive) add function can be written as follows:

 let rec (@) xs ys = match xs with | [] -> ys | x::xs' -> x::(xs' @ ys) 

Thus, the inner append ( @ ) splits the first list ( xs ) and uses the cons ( :: cons operator to build the resulting list. It is easy to see that there are n steps to add ( :: , where n is the length of the first list.