Re: O-notation

Richard Harter wrote:

> On Mon, 21 Nov 2005 10:40:40 -0500, Pat Farrell <pfarrell@xxxxxxxxxx>
> wrote:
>
>>Ronny Mandal wrote:
>>> for (i = 1; i<= n; i++)
>>> for (j = 1; j<=n; j = 2 *j)
>>>
>>> Since this contains two loops tht increments their index by 2*1, 2*2,
>>> 2*3 ...2*n, and the outer is linear I would say that the running-time
>>> is n(log n)^2.
>>
>>You'd be better off doing your own homework.
>
> Your statement, while true, is a disservice. Our hapless hero has
> given the right answer accompanied with an error in reasoning. The
> two loops do not increment "index by 2*1, 2*2, 2*3 ...2*n", they
> double it each time, i.e., j= 1, 2, 4, 8, ....

so more generally, it is
for (jp = 0, j=0; j<=n; j = 2 **(++jp))

Unhelpful was intentional, don't know if I agree with your use of
disservice.


--
Pat


.