For the pseudocode below for procedure Mystery(n), derive tight upper and lower bounds on its asymptotic worst-case running time f (n). That is, for the set of inputs including those that force Mystery to work its hardest, find g (n) such that f (n) (g(n)). Assume that the input n is a positive integer. Justify your answer.

Mystery (n)

1. if n is an even number

2. for i = 1 to n

3.	for j = n downto n/2
4.	print 1

5. else

6. for k = 1 to n/4

7. for m = 1 to n/4

8. print 2