Question

Please type, no handwriting!!! In case i cant see clear...

4. (5 Points) Describe best case, average case, and worst case in terms of Big O Notation. When implementing algorithms or data structures which two “Big O cases” are most important to consider and why?

5. (10 points) Bubble Sort and Selection Sort explain the similarities and difference between the two algorithms. What is the Worst Case Big (O) and why?

Answer 1

Answer 4:

We can have three cases to break down an algorithm:

1) Worst Case

2) Average Case

3) Best Case

Worst Case Analysis (Usually Done)

In the worst case examination, we figure upper bound on running time of an algorithm. We should know the case that makes most extreme number of tasks be executed. For Linear Search, the worst case happens when the component to be searched (x in the above code) is absent in the exhibit. At the point when x is absent, the search() capacities contrasts it and every one of the components of arr[] one by one. In this way, the worst case time many-sided quality of linear search would be Θ(n).

Average Case Analysis (Sometimes done)

In average case investigation, we take every single conceivable information and figure registering time for the greater part of the data sources. Aggregate all the computed esteems and separation the entirety by add up to number of information sources. We should know (or foresee) circulation of cases.

Best Case Analysis (Bogus)

In the best case investigation, we figure bring down bound on running time of an algorithm. We should know the case that makes least number of activities be executed. In the linear search issue, the best case happens when x is available at the primary area. The quantity of tasks in the best case is consistent (not subject to n). So time multifaceted nature in the best case would be Θ(1)

A large portion of the circumstances, we do worst case examination to dissect algorithms. In the worst examination, we ensure an upper bound on the running time of an algorithm which is great data.

The average case examination isn't anything but difficult to do in the greater part of the down to earth cases and it is infrequently done. In the average case examination, we should know (or foresee) the scientific appropriation of every single conceivable info.

The Best Case examination is false. Ensuring a lower bound on an algorithm doesn't give any data as in the worst case, an algorithm may take a very long time to run.

For a few algorithms, every one of the cases are asymptotically same, i.e., there are no worst and best cases. For instance, Merge Sort. Union Sort does Θ(nLogn) activities in all cases. A large portion of the other arranging algorithms have worst and best cases. For instance, in the average execution of Quick Sort (where rotate is picked as a corner component), the worst happens when the info exhibit is as of now arranged and the best happen when the turn components dependably partition cluster in two parts. For inclusion sort, the worst case happens when the exhibit is turn around arranged and the best case happens when the cluster is arranged in an indistinguishable request from yield.

Answer 5 :

Reason FOR COMPARISON	Bubble Sort	Selection Sort
Basic	Adjoining component is looked at and swapped	Largest component is chosen and swapped with the last component (if there should arise an occurrence of climbing request).
Best Case Complexity	O(n)	O(n^2)
Efficiency	Ineffecient	Enhanced proficiency when contrasted with bubble sort
Method	Exhanging	Selection
Speed	Slow	Quick when contrasted with bubble sort

DEAR RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT. THANK YOU!!