968 views

2 Answers

1 votes
1 votes
Here upper bound means that Heap sort needs Maximum time O(nlogn) ..that is maximum it may take such time or has to perform such amount of work.  but in best cases it(not specifically heapsort...any program i am talking about) may take very less amount of time..theoriticaly in best case it may take O(1) or O(logn)  time i.e very less amount of time

but worst case lower bound means that the problem can't be solved less than the time mentioned in relation like Omega(nlogn)  

whatever the input order/size is ...for example here you can't make a merge sort sooner that nlogn time proportion
0 votes
0 votes
Uper bound means maximum time taken by process to complete .

Worst lowe bound means in worst case minimum time needed to complete process. ie. merge sort take time theeta(nlogn) i.e. maximum time O(nlogn)  and minmum time omega(nlogn).

Related questions

0 votes
0 votes
1 answer
3
P Srinivas Rao asked Oct 9, 2016
311 views
For f(n)= 2n2+3n , O(n3) and o(n3) both are correct then what do both mean in this. As Big oh is used to reprsent the tighest upper upper bound but it is not representing...
0 votes
0 votes
1 answer
4
sh!va asked Jun 16, 2016
886 views
In gate 2003 cse question, i read that tightest upper bound of selection sort is O(n), which occurs only when ( n-1) swaps. My doubt is " tightest upper bound " is kuust ...