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?
1 answer
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