MIT's Introduction to Algorithms, Lectures 20 and 21: Parallel Algorithms

You're viewing a comment by jim and its responses.

jim Permalink
April 06, 2011, 07:06

In the handout (lecture 21, page 2 of 2), the critical path length for mergesort with plain merge (not parallel merge) was given as T_inf(n) = T_inf(n/2) + Theta(1) = Theta(n).
Shouldn't this be T_inf(n) = T_inf(n/2) + Theta(n) = Theta(n)?

Reply to this comment

Comment Responses

jim Permalink
April 06, 2011, 07:25

Checked the video. The notes were wrong. The video was right with
T_inf(n) = T_inf(n/2) + Theta(n) = Theta(n).
Otherwise the result would have been Theta(log n).

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.