PART 2:

Evaluate the following code segment and determine the O(.) for the best and worst cases. Assume an input size of n.

sum = 0

i = n

while i > 0 :

sum += i

i = i / 2

4.2 Determine the O(G) for each of the following functions, which represent the number of steps required for some algorithm. (a) T(n) = n2 + 400n + 5 (b) T(n) = 67n + 3n (c) T(n) = 2n + 5n log n + 100 (d) T(n) = log n + 2n2 + 55 (e) T(n) = 3(2n) + n8 + 1024 (f) T( n, k) = kn + log k (g) T(n, k) = 9n + k log n + 1000