gXa's blog

Divide and conquer
By gXa, history, 9 years ago, In English

Can somebody help me in finding running time of algo: Partitions the problem into two sub-problems of sizes n/5 and 7n/10, and spends O(n/log n) time to divide and combine the solutions.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

We denote running time by T(n). Then T(n)<=T(n/5)+T(7n/10)+an/log(n), where a is constant. Obviously, if running time of combining is asymptotically exactly O(n/log n), then T(n) cannot be less. So if we want to prove that T(n)=O(n/log n), then it is sufficient to prove that for some constant c: T(n)<=cn/log n. Let's try to do this by induction.

We can prove the base of induction for arbitrary large N: if we pick c big enough, we will have T(n)<=cn/log n for all n <= N. So the most interesting part is step. Here we have 

T(n) <= T(n/5)+T(7n/10)+an/log(n) <= c(n/5)/log(n/5)+c(7n/10)/log(7n/10)+an/log(n) =
= cn/log(n)*(log(n)/(5log(n/5))+7log(n)/(10log(7n/10))+a/c)

We see that log(n/5)=log(n)-log(5), and so the first summand in the brackets tends to 1/5 when n tends to infinity; similarly, the second summand tends to 7/10. So we can choose N in such a way that for n>=N first summand is not greater than, say, 1/5+1/100, and second is not greater than 7/10+1/100. Then we can choose c big enough to prove induction base for n<=N and to make a/c less than 1/10-2/100. Therefore we obtain that the expression in brackets is not greater than 1, so we proved the induction step (we used the induction assumption for n/5 and 7n/10). The answer is O(n/log n)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 12   Vote: I like it +3 Vote: I do not like it

    Use Latex to format equations, i.e. put the formulas inbetween dollar signs:

    → Reply