Comments on How to determine a precise upper bound of the growth rate with a product series?
Parent
How to determine a precise upper bound of the growth rate with a product series?
I'm trying to determine the growth rate of an algorithm.
The variables are:
n: the input size; it's an integer >=1.
p: a coefficient in the range (0, 1).
So far, I've been able to determine a growth rate upper bound in terms of a product:
product(log(n*p^k) / log(1/(1-p))),
for k from 0 to (log(n)/log(1/p));
How can I transform that series into big-O notation?
Of course, I can just consider an upper bound by taking k==0 in the whole series, and say it's in
O((log(n) / log(1/(1-p))) ^ (log(n) / log(1/p) + 1));
But is there a more precise upper bound thanks to the increasing value of k?
I've been able to extract the denominator, as it doesn't depend on k.
product(log(n * p^k) / log(1/(1-p))),
for k from 0 to (log(n)/log(1/p));
=
product(log(n * p^k))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
And now, I can separate the logarithms into a sum, to extract the k from the exponent (I'm not sure if it helps).
product(log(n * p^k))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
=
product(log(n)+log(p)*k)
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
And now it looks like (a+b)^x, but not exactly. log(n) is always log(n). But log(p)*k is increasing in magnitude (and <0).
We can invert the log to get a negative sign, which makes it more normalized:
product(log(n) + k*log(p))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
=
product(log(n) - k*log(1/p))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
And it is interesting to see that in the last iteration where k=log(n)/log(1/p), the multiplicand is log(n) - log(n)/log(1/p)*log(1/p), which is equal to 1.
The multiplicand is at a maximum in the first iteration, and then decays to 1. Is that decay powerful enough to counter the number of elements in the series?
Post
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| alx | (no comment) | Mar 27, 2026 at 23:03 |
I suspect there's a factorial here. Ok, let's try to isolate the k.
product(log(n) - k*log(1/p))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1)),
for k from 0 to (log(n)/log(1/p));
=
product(log(1/p)*(log(n)/log(1/p) - k))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1)),
for k from 0 to (log(n)/log(1/p));
And then we can move out that factor from the product, as it doesn't depend on k.
product(log(1/p)*(log(n)/log(1/p) - k))
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
=
product(log(n)/log(1/p) - k)
* log(1/p) ^ (log(n)/log(1/p) + 1)
/ log(1/(1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
=
product(log(n)/log(1/p) - k)
* (log(1/p)/log(1/1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
And now we can see it nicely that there's a factorial.
product(log(n)/log(1/p) - k)
* (log(1/p)/log(1/1-p)) ^ (log(n)/log(1/p) + 1),
for k from 0 to (log(n)/log(1/p));
=
(log(n)/log(1/p))!
* (log(1/p)/log(1/1-p)) ^ (log(n)/log(1/p) + 1)
And here it is. We got rid of the product, and have it as a factorial (which is still a product, but one more well known).
And let's try to move that log(1/p) to the denominator, to normalize it further:
(log(n)/log(1/p))! * (log(1/p)/log(1/1-p)) ^ (log(n)/log(1/p) + 1)
=
(log(n)/log(1/p))! / (log(1/1-p)/log(1/p)) ^ (log(n)/log(1/p) + 1)
(I might have made some mistakes, though; the graph is similar to what I get experimentally, but has some important differences.)
1 comment thread
0 comment threads