1. Let n(m) = n(n 1)... (n m + 1). Express n in terms of n(3),...

 

Transcribed Image Text:

1. Let n(m) = n(n 1)... (n m + 1). Express n in terms of n(3), n(2) - 2. Evaluate k(k 1)2k. - k=1 - and n(1). 3 and 4. Prove, for each pair of expressions (f(n), g(n)) below, whether f(n) is O, o, N, w or of g(n). In each case, it is possible that more than one of these conditions is satisfied. 3. f(n) logn, g(n) = log(logn). = 4. f(n) n where k is a positive integer, g(n) = cn, where c> 1. = 5. Derive a lower bound to search for a number that is present in a sorted list of n numbers by comparisons. 1. Let n(m) = n(n 1)... (n m + 1). Express n in terms of n(3), n(2) - 2. Evaluate k(k 1)2k. - k=1 - and n(1). 3 and 4. Prove, for each pair of expressions (f(n), g(n)) below, whether f(n) is O, o, N, w or of g(n). In each case, it is possible that more than one of these conditions is satisfied. 3. f(n) logn, g(n) = log(logn). = 4. f(n) n where k is a positive integer, g(n) = cn, where c> 1. = 5. Derive a lower bound to search for a number that is present in a sorted list of n numbers by comparisons.