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?
The second algorithm uses less space, but the first does fewer comparisons in general. In both algorithms you compare every node with alphabetically with the target until you find one that’s greater. In the second you also test each of those nodes except the last to see whether it has the desired property; in the first, however, you test only those back to the first one (working backwards) that has the desired property.