#formulating Divide and Conquer recurrence equations

3 messages · Page 1 of 1 (latest)

wise atlas
#

I am a complete complete beginner to algorithms. I also have a very basic level understanding of math. This is my second week of following a Algorithms course so to keep up in class I'm reading the book: "Introduction to Algorithms" chapter 2. In that chapter there's this piece of text:

"
"Although the pseudocode for MERGE-SORT works correctly when the number of elements is not even, our recurrence-based analysis is simplified if we assume that the original problem size is a power of 2. Each divide step then yields two subsequences of size exactly n/2. In Chapter 4, we shall see that this assumption does not affect the order of growth of the solution to the recurrence. We reason as follows to set up the recurrence for T(n), the worst-case running time of merge sort on n numbers. Merge sort on just one element takes constant time. When we have n > 1 elements, we break down the running time as follows.
Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = Θ(1).
Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time.
Combine: We have already noted that the MERGE procedure on an n-element subarray takes time Θ(n), and so C(n) = Θ(n).
When we add the functions D(n) and C(n) for the merge sort analysis, we are adding a function that is Θ(n) and a function that is Θ(1). This sum is a linear function of n, that is, Θ(n). Adding it to the 2T(n/2) term from the “conquer” step gives the recurrence for the worst-case running time T(n) of merge sort:

*see picture*

MLA 9th Edition (Modern Language Assoc.)
Thomas H. Cormen, et al. Introduction to Algorithms. The MIT Press, 2009.

APA 7th Edition (American Psychological Assoc.)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein. (2009). Introduction to Algorithms: Vol. Third edition. The MIT Press.
"

And there are just so many questions arising from this. I will write them below:

static mountainBOT
wise atlas
#
  1. "We reason as follows to set up the recurrence for T(n), the worst-case running time of merge sort on n numbers." earlier in the chapter the book specified: "we let T(n) be the running time on a problem of size n.". If I understand correctly, a recurrence or recurrence equation describes the running time of an algorithm that contains a recursive call to itself. And if I am not mistaken, it is usually expressed as a function of T(n), T(n) being the run time of a problem of size n. Right now, I am not completely understanding what the difference is between T(n) and Θ(n). What do they mean? How do they differ from each other? How are they related to recurrence equations? And when do you use one instead of the other?

  2. "Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = Θ(1)." The confusing I have here is related to the confusing I have in confusing number 1. i understand that computing the middle of the subarray takes a constant amount of time, regardless of the size of the subarray. And I assume that D(n) refers to the amount of time spent during the Divide part on a problem of size n, is that correct? So why is D(n) = Θ(1)? What does Θ(1) mean exactly? 1 second? 1 unit of time? 1 multiplied by theta? What even is theta? I have the same questions for this part: "Combine: We have already noted that the MERGE procedure on an n-element subarray takes time Θ(n), and so C(n) = Θ(n).".

  3. "Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time. " I am confused why the running time of the Conquer part is 2T(n/2). And why is it expressed in T this time instead of theta? What does each factor in 2T(n/2) mean exactly and where did they get the value of each factor from?