Problem 1

You are given the following expressions.

a. Solve these expressions to find () in terms of .

b. What are the complexities of these functions?

c. If () and () represent the time requirements of two algorithms, would one algorithm run faster than the other? Give a clear explanation.

Problem 2

You are given an array A that has n elements. Write an algorithm to find if all elements in this array are unique (there are no duplicate elements). Your algorithm must return true if there are no duplicate elements in the array, and false otherwise.

a. Write the pseudocode of your algorithm.

b. Write a formula that defines the complexity T(n) of your algorithm. (Your formula must include some summation terms)

c. Solve this formula to find the order of growth (complexity) of your algorithm.

d. What is the best case complexity of your algorithm? Explain.

Problem 3

If bubble sort makes no changes on its pass through a list, the list is sorted and the algorithm can be stopped.

a. Write a pseudocode of the bubble sort algorithm that incorporates this method.

b. Prove that the best case efficiency of the improved version is linear.

c. Prove that the worst case efficiency of the improved version is quadratic.

Problem 1 Problem 3 You are given the following expressions. If bubble sort makes no changes on its pass t1(n)=t1(n1)+nt1(1)=1t2(n)=i=0nj=0i1 through a list, the list is sorted and the algorithm can be stopped. a. Write a pseudocode of the bubble sort algorithm that incorporates this method. b. Prove that the best case efficiency of the improved version is linear. c. Prove that the worst case efficiency of a. Solve these expressions to find t(n) in the improved version is quadratic. terms of n. b. What are the complexities of these functions? c. If t1(n) and t2(n) represent the time requirements of two algorithms, would one algorithm run faster than the other? Give a clear explanation. Problem 2 You are given an array A that has n elements. Write an algorithm to find if all elements in this array are unique (there are no duplicate elements). Your algorithm must return true if there are no duplicate elements in the array, and false otherwise. a. Write the pseudocode of your algorithm. b. Write a formula that defines the complexity T(n) of your algorithm. (Your formula must include some summation terms) c. Solve this formula to find the order of growth (complexity) of your algorithm. d. What is the best case complexity of your algorithm? Explain