On Tue, 23 Feb 1999, Jakob Andreas Baerentzen wrote:
> On Tue, 23 Feb 1999, Herry Budiutama wrote:
> > This sounds like homework. :) Here's O(n)...
>
> are you sure? While the algorithm is terse, elegant and probably works, I
> think the implementation of strlen undermines your claim. I seem to recall
> that strlen must traverse the entire string. That taken into account, I
> think the algorithm is probably O(n^2), although simply transferring the
> string length to a variable would fix it, and since any letter of p1 is
> visited only once, your algorithm would then be O(n) ... i think ;-)
Of course, I assume he knows how to optimize :) I did it in 10 min
afterall. The underlying algorithm is O(n), I believe.
Herry
