m*********s
发帖数: 5 | 1 数学家们,
f(n) <= 4*f(n/2) + 2n
What would be the solution to this recurrence inequality?
I seemed to remember this is related to the divide-and-conquer algorithm and
to O(n*logn)... Right now my mind is so full and tired that I cannot think or
reason coherently, so please help me. If this f(n) <= 4*n^2, then my research
finally has some hope!!!
Thanks a million!!!!!! | a*******a
发帖数: 33 | 2 let g(n)=f(n)+2n,
then g(n) <= 4*g(n/2),
hence g(2^n)<=2^(2n)g(1)
or
research
【在 m*********s 的大作中提到】
: 数学家们,
: f(n) <= 4*f(n/2) + 2n
: What would be the solution to this recurrence inequality?
: I seemed to remember this is related to the divide-and-conquer algorithm and
: to O(n*logn)... Right now my mind is so full and tired that I cannot think or
: reason coherently, so please help me. If this f(n) <= 4*n^2, then my research
: finally has some hope!!!
: Thanks a million!!!!!!
|
|
