Question

Let A and B be two data lists. Concatenation of the list A and another list B is defined to be equal to B, if
A is null; and is defined to be equal to concatenation of head of A with the concatenation of tail of A and
B, otherwise (where head of A is the first element of A, and tail of A is the list A after removing its head).
What is the time complexity behavior of this procedure for concatenation of lists?

Answer 1

I interpret this as:

if (A==φ)A|B == B
else A|B = Ha|Tab

But then we're defining A|B using Tab,
which is the tail of A|B. Sounds to me a circular definition.

Can you please clarify the definition, or give your comments?

Answer 2

well question related to advance analysis of algorithm i.e. BIG O

Answer 3

Are you already familiar with linked lists?

We assume A and B are singly linked lists, i.e. linked in the forward direction only.

To attain the end of a list, the node pointer must traverse every node from head to tail.

The number of operations is therefore n, where n=size of linked list A. Once the end-node is reached, it will then be made to point to, and replace, the head of list B. This means that the size of B is irrelevant.

Can you now find the big O from the above description?

Answer 4

well sir Thanks for the answer I understood the description but I am new in this subject.I still cant find big O.Really thankful for your act of kindness