Problem-1: Find two algorithms to solve problems and analyze their tradeoffs per

Question

Problem-1: Find two algorithms to solve problems and analyze their tradeoffs performances Explanation: Some problems can be solved in different ways-sometimes taking less time-but others taking more time- but less storage space. Sorting a deck of cards into order: If you were physically wedged in a very small space, with no way to lay out the cards-you might try taking a card off the top of the deck and moving it to roughly the right place in the stack-then going through the deck fixing up mistakes, over and over until it was all in the right order. It would take a lot of time-but if you were in a tight space, it would work. If you had a nice large table to work on - you might try spreading all of the cards out then just picking them up in the right order. MUCH faster - but needing a large amount of space. Computer algorithms (inclading those for sorting cards into order) have simalar "trade-offs". You can easily end up with two algorithms, one faster than the other-but also needing more memory. In that case, there is no one Best" algorithm It all depends on your context. In a tiny "embedded computer with not much memory that only has to solve the problem once-you maybe don't care if it takes half a second to do the job. But in a video game that has to do absolutely everything 60 times per second- and your algorithm isn't allowed to use more than 1% ofthe available time-then maybe you dn't mind wasting some memory if it gets the job done in the 1/6,000 of a second you have to do it

Explanation / Answer

The two algorithms we will be considering here are quick_sort() and merge_sort().b

As the example given in question with a deck of cards, first scenario i.e. choosing top card and placing it in it's right position from top, mataches with quick_sort() as it does same things like it choose a element, we name it 'pivot' element, know we traverse list once and place it into it's actual/ correct position as it will be in sorted list, without taking any extra space.

While the next scenario, in which use whole table as to spread cards and then from it we choose one by one right cards and sort the deck of cards. In merge_sort() we do exactly same as in scenario, we use extra space so that we can divide the list into two parts, then go to recursively divide the produced list until only one element is left. Then using this several one element lists we can pick that is minimum and then so on to create the whole list.

Anaylsis and tradeOff's with performance:

Quick_Sort(List):

Time Complexity:

Best Case: O(n*logn)

Worst Case: O(n2)

Average Case: O(n*logn)

Space Complexity: O(1). As no extra space is used.

Merge_Sort(List):

Time Complexity:

Best Case = Worst Case = Average Case = O(n*logn)

Space Complexity: O(n). As an extra space(auxillary space) of list size is needed.

As we can see from above,

In Merge_Sort() time taken to sort a list/ deck of cards is always less than or equal to Quick_Sort(List), but for this to achieve, it makes a tradeOff's with space(performance) and uses extra space for it's operation.

Similarly, In Quick_Sort(), it tradeOff's with time taken to solve operation, so that it can work without any extra space.

I hope you understood the comparision here, but if you have no knowledge of these sorting techniques, don't worry I have provided refrences to them. Aslo, in case of any doubt you can comment below.

Refrences:

Quick_Sort(): https://www.geeksforgeeks.org/quick-sort/

Merge_Sort(): https://www.geeksforgeeks.org/merge-sort/

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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