Review Suggested Edit

You can't approve or reject suggested edits because you haven't yet earned the Edit Posts ability.

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?

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));
```
$$
\Pi_{k = 0}^{\log n / \log(1/p)} \log(np^k)/\log(1/(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?

series computational-mathematics

Communities

Review Suggested Edit