-1
$\begingroup$

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]

CODE In C#

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.

$\endgroup$

closed as unclear what you're asking by D.W., Raphael Mar 14 '14 at 16:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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
1
$\begingroup$

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|)$.

$\endgroup$

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