some help understanding a computational complexity

[pamela fluente]

I am trying to determine a "simpler" upper bound for ( a problem which
had the following comp complexity) :

sum ( for r = 2 to sqrt(n) ) of O( log( n / r) )

what can i say? Is this less than O(n^k1) or, better, less than
O(log(n)^k2) for some k1, k2 ?

What is a simpler tightest bound one can give for this complexity ?

Thank you

Pam

[from...@hotmail.com]

I'm n ot s ure it ma kes sense to add big O's directly (does it?).
Did you mea n...

O(s um(r=2 to sqrt(n)) of (l og(n/r)))

...?

(RIGHT?)

Here are a few more hints:

> log(n/r) can be simplified to log(n) - log(r)
> a series of the form sum(for n = 1 to k) simplifies to n(n+1)/2
> with big O notation, you are allowed to drop constants (as you
probably already know)

I hope this helps. Let me know if you need further assistance or
can't get it on your own. I suspect it's something like:

O(n*ln(n))

...but I haven't worked it out. Hopefully I'm not crazy :). Is there
any particular spot where you are having trouble in doing this
yourself?

-cplxphil

[pamela fluente]

On 4 Feb, 04:19, fromth...@hotmail.com wrote:

> I'm n ot s ure it ma kes sense to add big  O's directly (does it?).
> Did you mea n...
>
> O(s um(r=2 to sqrt(n)) of (l og(n/r)))

Ah very good question! That's why i am asking you guys ;-)
Let me express and refine "in words" what i intended to mean here: so
you can suggest the rigorous math formulation.

I simply mean that complexity of the problem can be reduced to a loop,
for r = 2 to sqrt(n), of "subproblems".

Each subproblem (within this loop) has, in turn, a complexity that is
the logarithm of a quantity which
decreases, with hyperbolic rate, from ( n/2 - sqrt(n) + 1 ) to 2, in
( sqrt(n) - 1 ) equidistant steps, 2 ... sqrt(n).

My intuitive guess was here that the overally complexity might be
bounded by O(sqrt(n)).
Of course, if it turned out that the iperbolic decrease rate is enough
to arrive at O(n*(ln(n))^k), or better O((log(n))^k), it would be
good.

>
> ...?
>
> (RIGHT?)
>
> Here are a few more hints:
>
>  > log(n/r) can be simplified to log(n) - log(r)
>  > a series of the form sum(for n = 1 to k) simplifies to n(n+1)/2
>  > with big O notation, you are allowed to drop constants (as you
> probably already know)

Yep. I know that the sum of logs is a log of a product. What i wanted
to see is actually
how to frame better and set up formally the general computation.

-P

[christian.bau]

If 2 <= r < sqrt (n), then sqrt (n) <= n / r <= n / 2.
Therefore log (n) / 2 <= log (n / r) <= log (n).
So for the numbers being added, r at most adds a factor of 1/2 and can
be ignored for O () calculations.

So we with the sum of sqrt (n) terms, each O (log n), for a total of

O (sqrt (n) * log (n)).

[pamela fluente]

On 4 Feb, 15:07, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:

Thank you christian. That would be the complexity assuming that at
each step i have log(n).

I have, at each step of the loop, something like log(f(n)) where f(n)
decreases rapidly
at each step of the loop, going essentially from a fraction of n to
the constant 2 (say with the rate of an hyperbola).

So i would expect being able to consider a tighter upper bound,
possibly <= O (sqrt (n)). Is this reasoning wrong ?

-Pam

[christian.bau]

On Feb 4, 2:44 pm, pamela fluente <pamelaflue...@libero.it> wrote:
> On 4 Feb, 15:07, "christian.bau" <christian....@cbau.wanadoo.co.uk>
> wrote:
>
> > If 2 <= r < sqrt (n), then sqrt (n) <= n / r <= n / 2.
> > Therefore log (n) / 2 <= log (n / r) <= log (n).
> > So for the numbers being added, r at most adds a factor of 1/2 and can
> > be ignored for O () calculations.
>
> > So we with the sum of sqrt (n) terms, each O (log n), for a total of
>
> > O (sqrt (n) * log (n)).
>
> Thank you christian. That would be the complexity assuming that at
> each step i have log(n).
>
> I have, at each step of the loop, something like log(f(n)) where f(n)
> decreases rapidly

Please re-read my post. I took into account that you are not summing
log (n), but log (n / r).

Because you only add values for r <= sqrt (n), n / r is at least >=
sqrt (n). (For example, n = 1,000,000; r <= 1,000; n / r >= 1,000).

log (sqrt (n)) = 1/2 log (n). So dividing n by r doesn't make that
much difference; the values that you add are at least (log (n) / 2)
and at most log (n). Summing log (n / r) instead of log (n) reduces
the sum at most by 50%.

[pamela fluente]

On 7 Feb, 00:28, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:

>
> Please re-read my post. I took into account that you are not summing
> log (n), but log (n / r).
>
> Because you only add values for r <= sqrt (n), n / r is at least >=
> sqrt (n). (For example, n = 1,000,000; r <= 1,000; n / r >= 1,000).
>
> log (sqrt (n)) = 1/2 log (n). So dividing n by r doesn't make that
> much difference; the values that you add are at least (log (n) / 2)
> and at most log (n). Summing log (n / r) instead of log (n) reduces
> the sum at most by 50%.

Thank you. Now i see clearly what you mean. You are right. What
"bothers"
is the sqrt(n) "dimension", the rest being already "within" a logaritm
does not
reduce much the complexity, even if a lot of terms are deleted.

Thank you.

-Pam