This is the only 1 big question but divided into parts so please do answer all of them.

Discussion 2 Sorting Sort Algorithms What types of sorting do you know? List all of them. Describe one of them in English, using your own words. Explain their complexity in worst, average, and best cases. O(n) Sort We call input data restricted if it has to follow some rules. A restriction example is that the data is a sequence of numbers. Do you know an algorithm that sort a restricted data in complexity O(n), where n is the size of the list that you need to sort? In what cases does it work? What are the restrictions on the input data? Hint - such algorithm needs only to traverse the data once, see Exercise1 & Lab2 assignments. Algorithms Execution Time Assume that there are 2 algorithms that both solve the same problem, and both are O(n^2) complexity. Are they interchangeable? Assume that program uses Algorithm1 and program2 is essentially the same as program1 except that Algorithm1 is replaced with Algorithm2 of the same time complexity. Will it take the approximately the same time to execute program1 and program2 using the same input data (and otherwise equal conditions like CPU speed, memory, etc.)? Can O(n^2) algorithm be better than O(n log n) algorithm? Can O(n^2) complexity algorithm be better in usage than O(n log n) complexity algorithm? If yes, then in what cases