In **Part II** of this post a solution was given to the problem presented in **Part I**:

"* Can we implement an algorithm for repetitive prepends that will be run by P1 in linear time, in addition to its excellent linear performance of repetitive appends*?"

The solution is implemented within the function **my:prepend-iter()** that is defined in the following way:

< < <
< "
</ |

The first argument passed to this function, **pNumTimes,** is the number of times to perform the prepend operation on the initial sequence **pstartSeq, **which is passed as the second argument.

The third argument has an auxiliary purpose. As its name, **pInserts **suggests, it contains the accumulation of all sequences that are to be prepended to **pstartSeq**.

The idea is to produce the final result only when **pNumTimes** is zero, using at this time the accumulated prepends in **pInserts **and the initial sequence **pstartSeq**.

* The idea of the algorithm is to replace the repetitive prepend operations with repetitive append operations, which are carried out by the xslt processor with linear complexity*.

We notice that:

**y2s ++ y1s ++ xs =**

**reverse( reverse(y1s) ++ reverse(y2s) ) ++ xs** **(1)**

Or in general, if we have N sequences:

**y1s, y2s, …, yNs**

to be prepended to an initial sequence xs in that order,

**yNs ++ yN-1s ++ … y2s ++ y1s ++ xs =**

**reverse(reverse(y1s)++reverse(y2s) ++ …**

** … ++ reverse(yNs) ) ++xs** **(2)**

**Remarkably**, the argument of the outermost **reverse()** is a repetitive appends operation and it has only linear complexity with P1!

We have added N+1 **reverse()** operations, but each of them is of linear complexity, so the total complexity of implementing **(2)** is O(N).

Certainly, the function **my:prepend-iter()** we have demonstrated is a simplified case of the many different real world scenarios we may encounter that will require repetitive prepends. Nevertheless its use is sufficient to prove and demonstrate how such an O(N) algorithm can be constructed.

We could use essentially the same algorithm, with a modification that accepts as argument a function **next-prepend()**, which produces the next sequence to be prepended. To signal the end of the repetitive prepend operation, we can use a convention that **next-prepend()** will indicate this by producing some special sequence, such as the empty sequence.

In case you may be wondering how can a function be passed as an argument to another function in XSLT, do read about **FXSL**.