Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in.
Post a replyTopic review (newest first)
Thanks, know is cristal clear!! :)
When you have a divide and conquer algorithm, they do something on each step after they divide. O(n^d) is the cost of what they do on this step. So let's say my imaginary algorithm divides a list in half, then sorts each part of that list with bubble sort. The cost of the bubble sort is n^2, so d = 2.
Does anyone read the book "Algorithms" by Papadimitriou et al.? I found it to be an excellent book, just sometime need a little bit of explanation in some parts of it. For example, in chapter 2 about divide and conquer algorithms it presents a master theorem about the time complexity for this kind of algoritms. It saids something like this: 