CODEWITHSUNDEEP
algorithmasymptotic-complexitybig-o
user2644819
user2644819

Reputation: 1827

Asymptotic Analysis questions

I found a couple questions on geeksforgeeks.org that i can't seem to understand(#1 and #3). I was hoping someone could clarify the answers for me:

clarify whether true/valid or false

1.Time Complexity of QuickSort is Θ(n^2)

I answered true but it is false, why? If quicksort has a time complexity of O(n^2) and we know that Θ(g(n))={f(n) where c1*g(n) <= f(n) <=c2*g(n) and n >= n0} then doesn't that prove that it is true since c2*g(n) being the upper bound can equal f(n)?

2.Time Complexity of QuickSort is O(n^2) - true

3.Time complexity of all computer algorithms can be written as Ω(1)

This is true but i have no understanding of why this is true. A search algorithm can have a lower bound of Ω(1) assuming we find what we were looking for on the first element but how does this hold true for ALL computer algorithms such as insertion sort algorithm where the worst case is O(n^2)?

link: http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/

Upvotes: 3

Views: 3112

Answers (2)

Tanmoy Banerjee
Tanmoy Banerjee

Reputation: 1453

Time Complexity of QuickSort is Θ(n^2)----This means for every value of n, time taken by the algorithm to produce the output is equal to a function which is f(n)=n^2.but we know this is not true for quick sort because we know for some input, running time of quick sort may be equal to a function which is g(n)=nlogn. so we need to specify if it is worst,best or average case.It is correct to say "Worst case time complexity of quicksort is Θ(n^2)".

"Time Complexity of QuickSort is O(n^2)"---this means for each input value of n,running time of the algorithm is at most a function which is f(n)=n^2.This implies there exist some input, for which the algorithm has a running time which may be less than f(n)=n^2.we know best case time complexity of quicksort is g(n)=nlogn and g(n)< f(n).As this statement covers all the cases so the statement is true.

Similarly it is correct to say "Time complexity of quicksort is Ω(nlogn)".because this means running time of the algorithm is at least nlogn, and n^2>nlogn.

"Time complexity of all computer algorithms can be written as Ω(1)"---here 1 represent constant time function.the above statement implies: to execute any computer algorithms we need a minimum constant time.which is correct for all computer algorithms.

Upvotes: 4

invalid_id
invalid_id

Reputation: 804

The worst case scenario for QuickSort is O(n^2). But you expect it to run in O(n log n) time. Hence the running time of the algorithm varies per case and you cannot use the theta symbol to give the general running time of the algorithm.

And of course the lowerbound on the running time of any algorithm is constant time (Ω(1)). It doesn't have to reach this lower bound though but the algorithm should be run, and should have at least one operation.

Upvotes: 1

Related Questions