# Algorithm to find string

Given a string $w$, we want to find the last string in the list, that precedes alphabetically $w$ and ends with the same letter as $w$.

Example: $\text{ w=crabapple }$

$L=\langle \text{canary, cat, chickadee, coelacanth, collie, corn, cup }\rangle$ The answer has to be collie.

There are different algorithms to solve the above problem.

Algorithm 1:

We traverse the list, until we find the first word that is alphabetically greater than crabapple(in our case cup), keeping at a stack pointers to the nodes, that we have traversed.

We extract the pointers ono to one from the stack and we check the structs at which they point, until we find the first word that ends with e.

Is this algorithm the most efficient?

Algorithm 2:

We traverse the list, beginning from the first node, keeping a pointer at the last element, that we traversed and had the desired property.

How would you compare the complexity of the above two algorithms?

I think that the second algorithm is more efficient, because we find a node with the desired property and then we just have to compare this with the other ones.

However, at the first algorithm we are looking for a node, that satisfies one of the two desired properties and then we have to traverse all the remaining nodes, in order to find a node that satisfies also the second property.

Am I right? How can we find the complexity?

• So, is the complexity of both of them $O(n)$? – evinda Nov 25 '14 at 18:56
• @evinda: Yes, if you’re measuring by number of comparisons and tests. You never have to do more than $2n$. – Brian M. Scott Nov 25 '14 at 18:57