1 Replies - 1212 Views - Last Post: 29 January 2007 - 03:28 PM Rate Topic: -----

#1 EquinoX  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • 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