Suppose that we have a divide and conquer algorithm f(n) such that O(f(n))=O(min(a, b)+f(a)+f(b)) where a+b=n, then what is the worst time complexity of f(n) (explicitly)?

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Um_nik | 3395 |

3 | Radewoosh | 3344 |

4 | Benq | 3316 |

5 | LHiC | 3302 |

6 | Petr | 3293 |

7 | wxhtxdy | 3286 |

8 | mnbvmar | 3274 |

9 | yutaka1999 | 3190 |

10 | ainta | 3180 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 178 |

3 | PikMike | 164 |

4 | Vovuh | 163 |

5 | rng_58 | 161 |

6 | majk | 157 |

6 | 300iq | 157 |

8 | antontrygubO_o | 156 |

9 | Um_nik | 149 |

10 | kostka | 148 |

Suppose that we have a divide and conquer algorithm f(n) such that O(f(n))=O(min(a, b)+f(a)+f(b)) where a+b=n, then what is the worst time complexity of f(n) (explicitly)?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2019 21:41:19 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The worst case running time is . I'll provide a situation with this exact time complexity and prove the running time:

Suppose a line of length

N. We will consider it as "connected" and as colored with 1 color. You will be given queries, in each query you are given some positionP. with each query, what you will do is you need to look at the current line segment containing positionP. You must break this line at positionPand color only one side of the now-broken line with a new color. You will color the shorter part that you got. The queries will keep coming until you end with single "points" you can't break. This is the exact time complexity you gave: with each query I have a line of some lengthX, then I divide it at some random point and operate on the shorter part, and now I have 2 segments with length summed up toX.Proof of running time being : For each position, let's count the amount of times we colored it (the coloring is the only process we're actually putting time into in the problem). Note that if the current position had some color, and after an operation it had a different color, it means we colored it, and we colored it because when we broke its line, it came out on the smaller part. This smaller part is

at leasttwice as small as the previous segment it was in. Therefor, for each of theNpositions we do at most , so we proved the running time.If you wonder about the specific case when this happens, it's when

a=b, and the recurrence becomes:T(n) =O(n) + 2T(n/ 2), which is a well known recurrence that ends up on .