# SIT221 Data Structures and Algorithms Practical Task 2.2

## Practical Task 2.2

In this task, answer all the following questions and complement each answer with a detailed explanation.

1. Conduct a small research on the Introspective Sort, which is a built‐in sorting algorithm of the Array.Sort method that you referred to in task 2.1P. Is it a unique algorithmic solution or a combination of several sorting algorithms? Does this method result in an unstable sort; that is, if two elements are equal, their order might not be preserved? Or does it perform a stable sort, which preserves the order of elements that are equal? What is the time complexity of this sorting algorithm?

2. Task 1.1P asked you to develop / provided you with a number of the Vector<T> className’s methods (and properties), such as Count, Capacity, Add, IndexOf, Insert, Clear, Contains, Remove, and RemoveAt. What is the algorithmic complexity of each of these operations? Does your implementation match the complexity of the corresponding operations offered by Microsoft .Net Framework for its List<T> collection? The following link should help you to answer this question

https://msdn.microsoft.com/en‐us/library/6sh2ey19(v=vs.110).aspx

3.Is it true that θ(n^{2}) algorithm always takes longer to run than an θ(log n) algorithm?Explain your answer.

4. Answer whether the following statements are right or wrong and explain your answers.

n^{2} + 10^{6}n = O(n^{2})

nlogn = O(n)

nlogn = Ω(n)

logn = o(n)