Solutions to Introduction to Algorithms

An example of a real world situation that would require sorting would be if you wanted to keep track of a bunch of people's file folders and be able to look up a given name quickly. A convex hull might be needed if you needed to secure a wildlife sanctuary with fencing and had to contain a bunch of specific nesting locations. ## Exercise 1.1-2 One might measure memory usage of an algorithm, or number of people required to carry out a single task. Exercise 1.1-3 An array. It has the limitation of requiring a lot of copying when re-sizing, inserting, and removing elements. A.length i=1 i A.length = A.length+1 . This makes the asymptotics for the expected case Θ(A.length). ## Exercise 2.2-4 And so, Now, inductively assume that T (n) ≥ c n lg(n) where c = min(1/3, T (2)/2). So, T (n) ∈ Ω(n). Together with the first part of this problem, we get that T (n) ∈ Θ(n).