1. Calculate the running time of the function below. Assume that your function is implemented
by using array list
by using linked list
Show your calculation in most convenient notation. (Big O/Teta/Omega)
BUBBLESORT(A)
1 for I = A. length – 1
2 for j = aA.length
3 if A(j) < A ( j – I )
4 exchange a(j) with A (j-1)
2. Sort the following functions from slowest to fastest in terms of their growth.
n2.56,log(n!), nlogn, loglogn2
3. Prove using only the definitions of asymptotic notations
n2 is in O(2𝑛 )
n! is in Ω(2𝑛 )
logn is in Ө(Log64n)
4. Prove that 2n2 - 4n +9=ϴ(n2 ) using induction.
5. Is Big-O an equivalence relation? Show classes and prove your answer.
6. Calculate the running time of the loops below.
for (int i = 1 ; i < n2 ; i+=5)
print()
for (int i = 0 ; i < 2n ; i+=3i)
for (int j = 0 ; j <i ; j++)
if (j = target) break;
else print()
7. The program in below lasts 8 second, when the the input size of the algorithm is 10. What is the working time while problem size is 160, on the same computer?
// Input : an integer
// Output : an integer
Function myFun(n)
{
count = 0
for i=1 to log n
for j=i to i+5
for k=1 to i*i
count = count + 1
return count
}
Note: Do not email your homework or submit it through moodle. Your submissions will be handwritten. CONTACT : Teacher
