COMP1011 Exercises for Week 11
Computing 1A 05s2 Last updated Tue 19 Jul 2005 14:37
Mail cs1011@cse.unsw.edu.au

Tute Exercises Week 11

Complexity

We discussed the O-Notation in the lecture. However, although we analysed with take a function whose asymptotic work complexity depends on two parameters, we did not give the formal definition of O if the running time depends on more than one parameter. The definition is a straight forward generalisation of the simple case:

Definition

Let T(n1,..,nk) be a timing function, then T(n1,..,nk) is O(f(n1,..,nk)) if there exisits
  1. non-negative numbers n1,0 to nk,0 and
  2. a non-negative number c such that for all (n1,..,nk) > (n1,0,..,nk,0) we have T(n1,..,nk) <= c * f(n1,..,nk)

Questions

  1. Derive the timing function for substring (worst case).
    You can assume that Ttail (n) = 1
    substring:: String -> String -> Bool
    substring ""    str  = True
    substring str   ""   = False
    substring str1  str2 = 
      (prefix str1 str2) || (substring str1 (tail str2))
    
    prefix:: String -> String -> Bool
    prefix "" str = True
    prefix str "" = False
    prefix (s1:str1) (s2:str2) 
      | s1 == s2   = prefix str1 str2
      | otherwise = False
    
  2. Let n be the length of the first string, m the length of the second string accepted by substring as arguments (assume that n < m).. Show that

  3. Find the ``tightest'' O-class Tsubstring that is a member (assume that n < m).