classtest1.pdf t En) 20:41 1 of 166.309 Thumbnails 2 Complexity - 15 marks 1. Ar

Question

classtest1.pdf t En) 20:41 1 of 166.309 Thumbnails 2 Complexity - 15 marks 1. Are the following statements true or false? Prove your answer (a) It is possible for a function in O(n) to be in (n2) 13 (b) 2n314n2 1 E S(n) [3] (c) O(3) c(2 13 (d) The worst case of an algorithm runs in O(n2) time. It is possible for the algorithm to rurn in O(n3) time. [3] 2. You have a task to perform. If you perform the task on an unsorted array, it wil take (n2 time. However, if you perform the task on a sorted array, i takes (nlog(n)) time. If you are given an unsorted array as input, how would you perform the task as efficiently as possible? Explain your answer. [3

Explanation / Answer

Speacial Note : Big O and Omega are meant to measure how fast the running time increase when the size of input increase.

1 a.> Let's visit the definition of Big O notation (upper bound).

Big O notation : f(n)=O(g(n)) means that there are positive constants c and k (i.e c>0, k>0) such that

0<=f(n)<=c*g(n) for all n>=k. Now coming to the question, let's assume, statement (1.a) is true, then,

n^3=O(n^2) , then there must exist constants c and k such that

n^3 <=c*n^2 , for all n>=k ---------------(1)

Now divide (1) by n^2, we get,

n<=c , for all n>=k. But this is not possible, we can never choose a constant clarge enough that n will never exceed it, since n can grow without bound. Therefore our initial assumption is wrong and statement 1(a) is false.

1.b> Omega notation (lower bound): f(n)=Omega(g(n)) means  

means that there are positive constants c and k (i.e c>0, k>0) such that

f(n)>=c*g(n)>=0 for all n>=k. Similar to 1(a). Let's assume, that statement 1(b) is correct, then

2*n^3+14*n^2+1>=c*n ----------(1)

divide (1) by n, we get,

2*n^2+14*n+1/n>=c. ------------(2)

(2) is always true. There is always some n>k and c>0 for (2). Therefore our assumption is correct.

1(b) is True

1(c)> As 1(a) is false, a conclusion can be drawn from it, that is n^2=O(n^3), which basically says that functions of type f(n)=a*n^2+b*n+c are subset of O(n^3). Therefore O(n^2) subset of O(n^3).

Therefore 1(c) is false.

1(d) Yes, It is possible. n^2=O(n^3), You need to understand that worst case i.e O(n^2) is not tight upper bound here. Theta-Notation is used for tight upper bound. Therefore, an algorithm having worst case of running time in O(n^2) can run in O(n^3) if tight upper bound is considered. (I am just assuming its possiblity as this is what question asks.)

2> I have two cases here.

Case1. Unsorted array, theta(n)=n^2.

Case2. Sorted array, theta(n)=n*log(n)

If input size is small, then I can just use insertion sort (running time: O(n^2)) as it won't affect running time much. Now I have unsorted array having theta(n^2). Let's say I use an algorithm, A , then It must satisfy c1*n^2 <=f(n) <=c2*n^2 as theta(n^2) is for upper and lower bound. So whichever algorithm is used, It must satisfy the above case. Insertion sort algorithm will just do fine here as this is an unsorted array and we know that for sorted array, best running time of insertion sort is O(n). This algorithm is efficient.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.