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

• Tsubstring (n,m) is not in O(m)
• Tsubstring (n,m) is not in O(n * n)

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