# Data structures and algorithms Insertion, sorting and searching

1.(5 points) Use the following code to prove that INSERTION sort runs in θ(n2), deﬁne the coast and time of every line of code, and use them in your prove. 2. (5 points) specify the lowest Big-Oh Complexity of each Algorithm (Show Steps)

(a) (1 point) f(x) = 100x + 0.01×2.

(b) (1 point) f(x) = 0.01xlog2x + x(log2x)2.

(c) (1 point) f(x) = 2x + x0.5 + 0.5×1.25.

(d) (1 point) f(x) = 0.3x + 5×1.5 + 2.5×1.75.

(e) (1 point) f(x) = x2 + 5x + 1.

3. (5 points) Write a short recursive Python function that ﬁnds the minimum and maximum values in a sequence without using any loops.

4. (5 points) prove by induction, that for all n > 1 the sum of the squares of the ﬁrst n positive integers is given by the formula 5. (5 points) illustrate a complete trace of a merge sort of the following array. Show all the arrays using a tree diagram, how can you prove MERGE sort runs in O(nlogn) 6. (5 points) Demonstrate what happens when we insert keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be

h(k) = k mod 9