# big-o

Page 1 of 1

## 1 Replies - 1281 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=896dbb7e2dddf90105071427fa582cfc&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 EquinoX

• D.I.C Head

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)
Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }