COMP1011 Exercises for Week 11 | |
---|---|
Computing 1A 05s2 |
Last updated
Tue 19 Jul 2005 14:37
Mail cs1011@cse.unsw.edu.au |
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(n_{1},..,n_{k}) be a timing function, then T(n_{1},..,n_{k}) is O(f(n_{1},..,n_{k})) if there exisits
- non-negative numbers n_{1,0} to n_{k,0} and
- a non-negative number c such that for all (n_{1},..,n_{k}) > (n_{1,0},..,n_{k,0}) we have T(n_{1},..,n_{k}) <= c * f(n_{1},..,n_{k})
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