1. What’s the running time of T(n) = 4 * T(n/2) + n * log n

(The correct answer should be O(n^2) , sorry about previous mistake )

 O(n * log n)
 O(n^2 * log n)
 O(n^2)
 Master Method not applicable
 
 I selected the last answer for this problem because n * log n did not have an obvious d. The solution for this exercise is the third option if a = 4, b = 2, d = 1. Am I wrong to think of n * log n to be enclosed in parenthesis: (n * log n)^1 yielding me d = 1?
 
 3. Following is pseudo-code for binary search. A is a sorted array to be searched. p and r are indices into the array -- as in merge-sort. k is the element we are looking for. If k is in A we want to return the index in A where k is found. Otherwise return -1.

BinarySearch(A, p, r, k)

if p > r return -1

else

            q = (p+r) / 2

            if k == A[q] return q

            else if k < A[q] return BinarySearch(A, p, q-1, k)

            else return BinarySearch(A, q+1, r, k)

What is the recurrence relation for this code?

 T(n) = 2 * T(n/2) + n
 T(n) = 2 * T(n/2) + O(1)
 T(n) = T(n/2) + n
 T(n) = T(n/2) + O(1)
 
 I selected the last answer for this. Someone explained as to why in class, but I don't recall what was it. So a is the number of sub-problems, b is the time it takes to solve a sub-problem, while d is the time it takes to put the problem together to get a solution. What is a good way to approach this exercise? Apparently the number of sub-problems is 1. The time it takes to solve a sub-problem is T(n/2) where b is 2. I'm guessing that this is because of the dividing that occurs when searching through the sub-arrays. As for the last part, it's constant because there is no merging that goes on?
 
 4. What is the runtime for Binary Search? 

Hint: Even if you got the recurrence relation in the previous question wrong, you should be able to figure out the answer to this question from first principles.

 T(n) = O(n * log n)
 T(n) = O(log n)    
 T(n) = O(n^2)
 T(n) = O(n)
 
 Is it log n because of the Binary Search Tree?
 
5. Recall the inversion counter discussed in the videos. It returned the number of inversions in O(n * log n) time. Is it possible to modify that code to return the list of inversions in O(n * log n) time?

 Yes. It would be a straightforward change to the inversion-counting code.
 Yes, because the maximum possible number of inversions is n^2 and n^2 = O( n * log n ).
 No because the Master Method doesn't apply to algorithms that return lists.
 No because the maximum possible number of inversions is n^2 and n^2 grows faster than n * log n.
 
 I need a recap as to why the answer's the last option.

yxu22 wrote:

1. d is not 1. d is some number greater than 1 and less than 2.

If f(n) is the rest part after 4 * T(n/2), which is f(n) = n * log n in this question, then d is the largest power of n in f(n)

 

3. The answer is the last one.

a is the number of sub problem

b is how you would divide the main problem ( In binary search, we would divide the whole input into half.) , (You may have the same understanding in different words description)

d is the running time we need to solve the rest part of code except the recursion.

 

4. Yes

 

1. Why is 1 the largest power of d? Would it be incorrect to say that it's 1.99? 

Also, Is the last term always f(n)? Say instead of n log n it is n^2 (we would then have an obvious d; d = 2).

3. The number of sub-problems is 1 because we're always working with the same array, right?

vsluong4 wrote:

3. The number of subproblems is 1 because each time the function is called, it only calls itself again 1 other time.

BinarySearch(A, p, r, k){
if p > r return -1
else q = (p+r) / 2
if k == A[q] return q
else if k < A[q] return BinarySearch(A, p, q-1, k)
else return BinarySearch(A, q+1, r, k)

}

BinarySearch can only call itself 1 time, so a=1.

Compare this to merge sort
MergeSort(anArray){
.....
MergeSort(leftHalf);
MergeSort(rightHalf);
Merge(leftHalf, rightHalf);

}

Which calls itself twice each time it is run, so a=2.

Understood. Thank you. Do you know how to answer my 3rd question? For f(n) = n * log n, the log n part isn't taken into consideration when finding d; why is that? 

vsluong4 wrote:

We did cover logarithmic factors in the f(n) term in class.

Perhaps you should review that material.

But you need not worry about it.

I tried reading this yesterday but it was quite difficult to understand.

This is what tripped me: Since f( n ) = n * log n = Ω( n ) and the regularity condition holds, namely, a * f(n/b) = ¾ * n * log n = c * f(n) for c = ¾, we can apply case 3, and find T(n) = Θ(n * log n)

First it's from obtaining Ω( n ) from n * log n.