1 Prove formally that: (a) logon e O(n), for any base b > 2; (b) 2" E O(n!): (c) 2" & O(n) for any finite k. 2 Lists are defined recursively as follows: 1:=13:1 That is, a list is either empty (I) or obtained by concatenating (::) an element onto a smaller list. The size of a list is the number of elements it contains. The following functional program sort performs an insertion sort on a given list, making use of an auxiliary insert function to insert a given element at the correct position within the list: fun insert (x, []) = [x] | insert (x, h :: t) = if x