I made a method that appends a sequence to another sequence.

So: (append [1,2,3] [4,5,6]) = [1,2,3,4,5,6]


IEnumerable<int> Append(IEnumerable<int> xs,IEnumerable<int> ys)
    using(var iteratorX = xs.GetEnumerator())
    using(var iteratorY = ys.GetEnumerator())
        bool isTrueForX = false;
        bool isTrueForY = false;
        while((isTrueForX = iteratorX.MoveNext()) || (isTrueForY = iteratorY.MoveNext()))
            if(isTrueForX) yield return iteratorX.Current;
            else if(isTrueForY) yield return iteratorY.Current;

I would like to know what is the time-complexity of this algorithm.

  • $\begingroup$ Why do you think it is $O(\max(|xs|,|ys|))$? What makes you unsure? Please show your work in the question, and explain where you got stuck; that makes it more likely we can help you usefully. $\endgroup$
    – D.W.
    Mar 14 '14 at 15:48
  • $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Mar 14 '14 at 16:28

Your code defines the combined list implicitly by defining an iterator that iterates over list xs first and after reaching the end of that list iterates over ys.

If $T_1(l)$ denotes the time for a single call to the iterator of list $l$, $T_a(l)$ denotes the combined time for all calls needed to iterate ove $l$, and the combined list is called $x.y$, we find $$T_1(x.y) = {\cal O}(\max\{T_1(x),T_1(y)\})$$ and $$T_a(x.y) = T_a(x)+T_a(y).$$

The first one will typically be ${\cal O}(1)$ and the second one ${\cal O}(|x.y|)$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.