Growth of Functions and Relations (01 and O2). [14 Marks] (a) (7 Marks) Arrange the following...

 

Transcribed Image Text:

Growth of Functions and Relations (01 and O2). [14 Marks] (a) (7 Marks) Arrange the following functions on integers in increasing order of their growth rate. If f(n) is O (g(n)) but g(n) is not O ((n)) then f(n) must be below g(n). If they are each big-O of each other, then they must be on the same level. Take all logs to have base 2. f(n) = logn, f(n) = loglogn, f3(n)= logn, f4(n) = n5 +n /1000, f5(n) = n!+2", f6(n) = 2n 5nlogn, f7(n) = (n logn+n) (n +2). (1) (b) (7 Marks) Let R be the relation on the set of functions from Z+ to Z+ such that (f,g) belongs to R if and only if is (g). Show that R is an equivalence relation. Describe the equivalence class containing f(n) = n for this equivalence relation. Growth of Functions and Relations (01 and O2). [14 Marks] (a) (7 Marks) Arrange the following functions on integers in increasing order of their growth rate. If f(n) is O (g(n)) but g(n) is not O ((n)) then f(n) must be below g(n). If they are each big-O of each other, then they must be on the same level. Take all logs to have base 2. f(n) = logn, f(n) = loglogn, f3(n)= logn, f4(n) = n5 +n /1000, f5(n) = n!+2", f6(n) = 2n 5nlogn, f7(n) = (n logn+n) (n +2). (1) (b) (7 Marks) Let R be the relation on the set of functions from Z+ to Z+ such that (f,g) belongs to R if and only if is (g). Show that R is an equivalence relation. Describe the equivalence class containing f(n) = n for this equivalence relation.