Time Complexity Answers
===============================================================================

The Code
--------

    function IsAWord (token : string) : boolean

        if Rurlex -> SearchLexicon (token) then
            result true
        elsif length (token) <= 1 then
            result false
        end if

        for i : 1 .. length (token) - 1
            if Rurlex -> SearchLexicon (token (1 .. i)) then
                result IsAWord (token (i + 1 .. *))
            end if
        end for

        result false

    end IsAWord


1. Recurrence Relation
----------------------

Consider a call to IsAWord.
Let C(n) denote the number of times "SearchLexicon" is called, in the worst
case, for a token of length n.


C(0) = 1
C(1) = 1

For n >= 2:

Once we find a prefix that is a base-form, we don't look at any of the 
other n-1 prefixes (we result right away, with true or fals).  We can get
away without checking the others because of Ruritanian's prefix-free property.

So, if the first prefix is a base-form, the work is:
   C(n) = 1 +          % to see if the whole thing is in the lex
          1 +          % to see that the first prefix in the lex
          C(n-1)       % to check that what follows that prefix is a word

If the i-th prefix is a base-form, the work is:
   C(n) = 1 +          % to see if the whole thing is in the lex
          i +          % to see if any of the first i prefixes in the lex
          C(n-i)       % to check that what follows the ith prefix is a word

So, in general, the work is:
   C(n) = 1 + i + C(n-i), for some 1 <= i <= n

The value of i can be different at each level of recursion, and the value
of C(n) does depend on the particular values of i.  For example, if in the
original call to IsAWord i is (n-1), that is, if the (n-1)st prefix is
the first one that's in the lexicon, then
   C(n) = 1 + (n-1) + C(n - (n-1))
        = n + C(1)
        = n + 1

But if k=1 at every level of recursion, then
   C(n) = 2 + C(n-1)
Solving this recurrence relation (see below), we see that
   C(n) = 2n - 1
which is much more than n + 1, 

This is the worst case: when i=1 at every level of recursion.
So the recurrence relation for the number of times "SearchLexicon" is 
called, in the worst case, for a token of length n, is:

	-------------------------------------
	| C(0) = 1                          |
	| C(1) = 1                          |
   	| C(n) = 2 + C(n-1), for all n >= 2 |
	-------------------------------------


I don't expect students to recognize this tricky part about different 
i values at different levels of the recursion, so if they come up with 
any one version for any single i value, that's fine.  Eg:
   For all n >=2,
   C(n) = 2 + C(n-1)


2. Solution to recurrence relation
----------------------------------

n  |  C(n)
----------
0  |  1
1  |  1
2  |  3
3  |  5
4  |  7
5  |  9
6  |  11
7  |  13

Solution: C(n) = 2n - 1, for all n >= 1
(n=1 doesn't quite fit this pattern.)


3. Time to search Ruritanian lexicon
------------------------------------

Because SearchLexicon simply does a binary search of an array,
the time required is O(log r), where r is the number of base forms 
in the lexicon.


4. Overall time to check if a word is Ruritanian
------------------------------------------------

Consider a call to IsaWord with a token of length n, and where the
number of entries in the lexicon is r.

O(n) calls to SearchLexicon occur.
O(log r) time is needed per call.
Everything else is constant time, and nothing happens more often than
the calls to SearchLexicon.

Therefore, time for the call to IsaWord is O(n log r) overall.