Part:1

This part is all about runtime and space complexity analysis. When computing the runtime or space bounds, they should be as tight as possible. You will not receive any points if your bound is not tight enough.

Consider the following function, . What is the tightest upper bound (big-O notation) ? Explain why you choose that particular function as your answer.

To do that, you have to show, there exist two positive constants such that What are the values of ? Explain.

Rank the following functions by the order of growth rate ( that is, list them in a list, such that ). Partition your list into equivalent classes such that and are in same growth class or .

You have to prove your answer:

Lets assume a program starts with data. At each iteration, this program, divides the data into three equal parts and discard two of them. It divides the remaining part into 3 equal parts again and discard two of them. The program continues until the remaining part contain only one data. What is the upper bound for running time of this program?

Illegal pyramid scheme, starts with one person (level 0), he has to recruit 4 persons under him. Then those 4 persons (level 1) need to find 4 persons for each of them as shown in figure. Now those 16 people at level 2 need to find 4 people for each of them. If the recruitment process goes on this way, how many levels it would require to recruit all the people in the world? (Assume that, the world population is 7.5 billion.)