Re: O-notation

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

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, .... In consequence the two
inner loops are both O(log n). Of course, as you say, multiplying it
by 4 each time is also O(log n), but that has nothing to do with the
error in his reasoning.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.
.

Relevant Pages

  • Re: Binary to Decimal
    ... lmh86 wrote: ... > Can anyone suggest any other methods that does not implement built-in ... This sounds like some homework, ... hint you into some direction, ...
    (microsoft.public.dotnet.languages.vc)
  • Re: numbers to text
    ... You change by writing program in Prolog ... This is your homework and you should figure it out ... twenty, thirty, ...ninety the teens ... Another hint: the div and mod operators can be useful for such a function. ...
    (comp.lang.prolog)
  • Re: Which prices are fake?
    ... Of course Benford's law doesn't help here, but as a hint, it suggests ... since the trailing digits for such tend ... Martin Penderis wrote: ... > challenge to all, and if the wording sounds like homework, I would not ...
    (sci.stat.math)
  • Re: help with question
    ... Let me look at a content called a Lebesgue measure, ... PS This is not homework. ... Then look at the hint given by A N Niel in the thread "content 0". ...
    (sci.math)
  • Re: How do u SELECT this one? SELECT rank=count(*)
    ... When you are trying to get other people to do your homework, ... want to put more effort into yourself when you get a hint. ... schema are. ... Sample data is also a good idea, ...
    (microsoft.public.sqlserver.programming)