Computer Science CSC263H St. George Campus
Answer to Question 1.
January 18, 2018 University of Toronto
a. T(n) is O(n2). This is because for every n 2:
Solutions for Homework Assignment #1
(i) For every input array A of size n, the outer for loop of Line 3 consists of doing at most (n 1) iterations, and each such iteration causes at most (n 1) inner iterations of the nested for loop of Line 4; so a total of at most (n 1)(n 1) < n2 inner loop iterations are executed.
(ii) Each inner loop iteration, and each one of the statements in line 1, 2, 4 and 5, takes constant time (because each consists of a constant number of comparisons and additions).
So it is clear that there is a constant c > 0 such that for all n 2: for every input A of size n, executing the procedure strange(A) takes at most c · n2 time.
b. T(n) is ⌦(n2). This is not obvious because the for loop of Line 3 may end “early” because of the loop exit condition in Line 5: if the condition of Line 5 is satisfied then the procedure call immediately ends. Thus, to show that T(n) is ⌦(n2), we must show that there is at least one input array A such that the procedure takes time proportional to n2 on this input, despite the loop exit condition of Line 5. We do so below.
T(n) is ⌦(n2) because for every n 2:
(i) There is an input array A of size n, namely array A[1..n] = h0, 1, 2, 3, 4, …, n + 1i, i.e., the
array A such that for all i, 1 i n, A[i] = i+1, such that the procedure does not return in Line 5.
This is because for all i, 2 i n: (a) just before the loop of Line 4 is executed A[i 1] = (i 1)+1, (b) just after the loop of Line 4 is executed A[i 1] = i, and (c) since A[i] = i+1, in Line 5, we have that A[i] = A[i 1] + 1 and so the procedure does not return in Line 5.
Thus, with this specific input, each iteration of the outer for loop of Line 3 with i n/2 will in turn cause the execution of at least n/2 inner iterations of the nested for loop of Line 4.
So, for input A[1..n] = h0, 1, 2, 3, 4, …, n + 1i, there are at least n2/4 iterations of the inner for loop of Line 4.
(ii) Each inner loop iteration takes constant time.
Soitisclearthatthereisaconstantc>0suchthatforalln>1: thereissomeinputAofsizen (namely, A[1..n] = h0, 1, 2, 3, 4, …, n + 1i) such that executing the procedure strange(A) takes at least c · n2 time.
Important note: For many arrays A of size n, for example all those where A[2] 6= 1, those where A[2] = 1 but A[3] 6= 2, etc…, the execution of procedure strange(A) takes only constant time! This is because the execution stops “early”, in Line 5, on these arrays.
So to prove that the worst-case time complexity of strange() is ⌦(n2), a correct argument must explicitly describe some input array A of size n for which the execution of strange(A) does take time proportional to n2.
Note that since T(n) is both O(n2) and ⌦(n2), it is ⇥(n2).
1
Answer to Question 2.
a. A ternary (max) heap H with n elements can be represented by an array A with an associated variable A.Heapsize = n, such that the elements of H are in A[1..n]. The root of H is stored in A[1], and it contains an element with largest key. The children of A[i] (from left to right in H) are A[3i 1] (if 3i 1n),A[3i](if3in)andA[3i+1](if3i+1n). Fori>1,theparentofA[i]isA[bi+1c].
b.
c.
3
1. Consider a ternary heap A with n elements. Element A[i] is an internal node of the heap if and only
if (i↵) it has at least one child. So A[i] is internal i↵ A[3i 1] is an element of the heap, i.e., i↵
3i 1n. ThusA[i]isaninternalnodei↵ibn+1c. 3
2. A ternary heap A with n elements has height blog3(2n 1)c. To see this, note that a complete ternary tree of height h has:
• at most 30 +31 +…+3h = 3h+1 1 nodes, and 2
•atleast30+31+…+3h 1+1=3h+1 nodes. 2
So in a complete ternary tree, the height h and the number of nodes n are related as follows: 3h+1 n 3h+1 1. Thus, 3h 2n 1 and 3h+1 2n+1. Hence, log (2n+1) 1 h log (2n 1).
2233 Therefore h = blog3(2n 1)c = dlog3(2n + 1) 1e.
• Insert(A, key): Insert key into A.
Algorithm sketch: (This is identical to the Insert procedure for binary heaps that we saw in class.) First increment A.Heapsize by one. Then put the (element x with) key in A[A.Heapsize] (for sim- plicity, in this description we identify the element x with its key). Finally, “percolate x up”until it settles to the right place, i.e., until the parent of x is greater or equal to x. To do so, keep comparing x with its parent, and swap the two if x is greater.
• Extract Max(A): Remove a key with highest priority from A.
Algorithm sketch: (This is similar to the Extract Max procedure for binary heaps that we saw in class.) First return A[1], then store A[A.Heapsize] in A[1] (replacing the old content of A[1]) and decrement A.Heapsize by one. Let x be the element now in A[1]. To restore the max-heap property, “drip x down” until it settles to the right place, i.e., until x is greater or equal to each of its children. To do so, keep comparing x with its children, and if one of them is greater, then swap x with the greatest of its children.
• Update(A, i, key), where 1 i A.Heapsize: Change the priority of element A[i] to key and restore the heap ordering property.
Algorithm sketch: Let x be the element in A[i].
– If Update(A,i,key): increases the (key of) x, then “percolate x up” until it settles to the right place, i.e., until the parent of x is greater or equal to x. To do so, keep comparing x with its parent, and swap the two if x is greater. This procedure is similar to Insert above.
– If Update(A,i,key) decreases the (key of) x, then “drip x down” until it settles to the right place, i.e., until x is greater or equal to each of its children. To do so, keep comparing x with its children, and if one of them is greater, then swap x with the greatest of its children. This procedure is similar to Extract Max above.
2
• Remove(A, i), where 1 i A.Heapsize: Delete the element A[i] from the heap.
Algorithm sketch: Let x be the element in A[i]. One way to delete x is to first use the Update(A, i, key) procedure to change the key of x to “infinity” (a key greater than any other key in A). This will make x percolate up all the way to the root of the max-heap A. Then execute Extract-Max(A) to remove x.
Let h be the height of the max-heap A (recall that h = blog3(2n 1)c, where n = A.Heapsize). The worst- case time complexity the above algorithms is both O(h) and ⌦(h), because: (1) they never take more than time proportional to h, and (2) they each have at least one execution that does take time proportional to h (e.g., for Update(A, i, key), such an execution occurs when i = n, and the new key is greater than any other key in A: this execution makes the leaf x = A[n] percolate up all the way to the root of the heap). So the worst-case time complexity of the above algorithms is ⇥(h) = ⇥(blog3(2n 1)c) = ⇥(log3 n).
3