[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem


Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem
From: Chris Maloney <voldrani@xxxxxxxxx>
Date: Thu, 6 Dec 2012 14:13:19 -0500

On Thu, Dec 6, 2012 at 1:29 PM, Hermann Stamm-Wilbrandt
<STAMMW@xxxxxxxxxx> wrote:
> ...
>
> But if you have N real language words of length k, each single word can
> have at most  k*26 = O(1) neighbors.

But N and k are not independent.  The number of words (N) will depend
on the number of letters in each word (k), at least for small values
of k.  Obviously, the same relationship (probably something roughly
linear for very low k) wouldn't hold as k gets larger.  I guess, then,
that since the O() notation refers to things in their limits as the
numbers get large, then what you say is correct.  but of course, as k
gets large, then (in most languages except perhaps German) N goes to
zero.

I guess, that there's some ambiguity in the meaning of O(foo) when
switching back and forth between a purely theoretical discussion of an
algorithm, and a practical application.


Current Thread