- #1
homomorphism
- 19
- 0
Let's say I have some algorithm with complexity [tex]O(n^k)[/tex] for some constant [tex]k[/tex]. and let's say it runs in some time [tex]T[/tex]. Now, I want to implement a divide and conquer approach for this algorithm, by dividing the problem in half each recursion. So basically, the first time i run my algorithm it will run in time [tex]T[/tex], the second time it will be [tex]O(\frac{n^k}{2^k}) + O(\frac{n^k}{2^k})[/tex] [since I'm running my algorithm on both halves] so the time will be [tex] \frac{T}{2^k} + \frac{T}{2^k}[/tex]. and then when i run my algorithm again it will be [tex]O(\frac{n^k}{4^k}) * 4[/tex]. This means the time will be [tex] 4 * \frac{T}{4^k} [/tex].
So basically, for a worst case scenario, with infinite recursions, I should have some sum,
[tex] \sum_{i=0}^{\infty} \frac{T}{2^i^{(k-1)}}[/tex]
Where [tex]T[/tex] is a constant. does this look about right?
So basically, for a worst case scenario, with infinite recursions, I should have some sum,
[tex] \sum_{i=0}^{\infty} \frac{T}{2^i^{(k-1)}}[/tex]
Where [tex]T[/tex] is a constant. does this look about right?