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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Word Ladders as an exampl, Hermann Stamm-Wilbra | Thread | Re: [xsl] Word Ladders as an exampl, Dimitre Novatchev |
Re: [xsl] Word Ladders as an exampl, Michael Kay | Date | Re: [xsl] Word Ladders as an exampl, Dimitre Novatchev |
Month |