[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Word Ladders as an example of a "Find shortest pat

Subject: Re: 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
Re:  Word Ladders as an example of a "Find shortest pat
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

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.