big-o

Page 1 of 1

1 Replies - 1294 Views - Last Post: 29 January 2007 - 03:28 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=23358&amp;s=9e753c7a3a34a0f76f562bf9dd9d0327&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 EquinoX

Reputation: 1
• Posts: 63
• Joined: 19-January 07

big-o

Posted 29 January 2007 - 03:14 PM

I've had a quiz with big-o problems and I still don't get it, can you guys help me:

for (int j = 1; j<=20; j++)
sum++;

why does this run on the order of O(1)??

for (int k = n; k>0; k=k/2)
sum++;

why does this run on the order of O(log n)??
Is This A Good Question/Topic? 0

Replies To: big-o

#2 William_Wilson

• lost in compilation

Reputation: 207
• Posts: 4,812
• Joined: 23-December 05

Re: big-o

Posted 29 January 2007 - 03:28 PM

the first one runs in O(20) a fixed length, thus it is always reduced as 20 = 20*1 consider it a co-efficient thus: O(1) or constant time.

the second runs in a logarithmic time because it is relative to the numbers 0, n and each pass the counter is changed not by a linear amount, but k/2, this implies that it is dependent on n, but not linearly so it's O(logn)