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$

enter image description here

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.

  • $\begingroup$ And how can we find the complexity of the two algorithms? $\endgroup$ – evinda Nov 25 '14 at 18:54
  • $\begingroup$ @evinda: That depends on how you’re measuring complexity. By any reasonable measure they’re both linear in the length of the list. $\endgroup$ – Brian M. Scott Nov 25 '14 at 18:55
  • $\begingroup$ So, is the complexity of both of them $O(n)$? $\endgroup$ – evinda Nov 25 '14 at 18:56
  • 1
    $\begingroup$ @evinda: Yes, if you’re measuring by number of comparisons and tests. You never have to do more than $2n$. $\endgroup$ – Brian M. Scott Nov 25 '14 at 18:57
  • 1
    $\begingroup$ @evinda: A new thread would be better: more people will see it. This really isn’t my field at all, so it’s good to have other eyes on it. $\endgroup$ – Brian M. Scott Nov 25 '14 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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