b***e 发帖数: 1419 | 1 Exam the following example:
a(i,n) = 1/n
b(i,n) = 1/n + 1/(n*(lg lg ... lg n))
^^^^^^^^^^^^
i lgs in all
I guess these definitions satisfy all your condiction,
but contradict your conclusion. It's just a guess though,
point out where I'm wrong. I am not good at maths analysis
at all. I like discrete maths more. | b***e 发帖数: 1419 | 2 Sorry, I made a mistake, the example should be as follows,
a(i, n) = 1/n
b(i, n) = 1/n + i /(n * log n)
The key is the result of
1/n * (1/log n + 2/log n + ... + n/log n) = O(n/log n) |
|