Re: O-notation

Message from Pat Farrell <pfarrell@xxxxxxxxxx> on Mon, 21 Nov 2005
10:40:40 -0500:

>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.
>
>Hint:
> for (j = 1; j<=n; j = 4 * j)
> for (j = 1; j<=n; j = 2 * j)
>are the same O

Well, I forgot some important signs:

for (i = 1; i<= n; i++)
{
for (j = 1; j<=n; j = 2 *j)
{
//do something
}
}

--

RM
.