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