Welcome! Log In Create A New Profile

Advanced

Big O notation

Posted by united 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Forums Messages New
united
Big O notation
February 10, 2007 09:01AM
Can someone clarify the order log n and n log n. I have not really understand when an algorithm will be log n and n log n. Examples to support the explanation will be much appreciated. Thanks.
Reply Quote
ibasson
Re: Big O notation
February 14, 2007 12:30PM
Consider the following fragment:

for(int i; i<n;i=i*2)
sum++

The running time for this is O(Log N)
Suppose n = 32, then sum++ is escalated 5 times

2^5 = 32 (log 32 = 5)Base of 2, but we can ignore the base

See if you can figure out nlogn now
Reply Quote
fransisca
Re: Big O notation
April 02, 2007 02:40PM
Hi can u please explain a bit why the

for(int i = 1; i < n; i = i*2)
sum++;
is of O(logN).
Reply Quote
avatar
robanaurochs
Re: Big O notation
April 12, 2007 09:00PM
It's not.

the code 
for (int i = 0; i < n; i *= 2)
  {
  ++sum;
  }
runs for 1/2 n loops thus it is O(n)

An example of O(log2 n) is the binary search algorithm.
Reply Quote
SynNopSys
Re: Big O notation
June 04, 2007 08:24AM
that for loop never terminates!!!
Reply Quote
SynNopSys
Re: Big O notation
June 04, 2007 08:25AM
i.e. for (int i=0;i<n;i*=2)...
should initialize to 1
Reply Quote
avatar
ilanpillemer
Re: Big O notation
June 19, 2007 12:25PM
Yup, by that logic,

for( ; ; ) is O(n).

Heh. What is the Big O notation for an infinite loop.
O(woooooooaaahhhhhhhhhhhhhhhhhhhhhaaaaooooaanananweeeeeeeeeeeenotlongnowmylittlesmurflings)
Reply Quote
avatar
robanaurochs
Re: Big O notation
June 19, 2007 01:40PM
Sorry, silly little mistake. You're right, it's an infinite loop. The point should not be overshadowed by the mistake though. It should read: 
for (int i = 1; i < n; I *= 2)
  {
  ++sum;
  }
Reply Quote
AndreB
Re: Big O notation
June 19, 2007 05:26PM
The Rob returns. Hell Rob - where've you been?
Reply Quote
avatar
robanaurochs
Re: Big O notation
June 23, 2007 11:11AM
Hey André. Still here, just been very busy with the new job and someone special. grinning smiley
Reply Quote
avatar
CountZero
Re: Big O notation
July 19, 2007 06:50PM
I also want to say hi to Rob!!

Rob helped me 2 years ago!
Rob is the only person who can explain inheritance in a way that everyone can understand!

Thanks man!
smileys with beer
Reply Quote
Newer Topic Older Topic
Sorry, only registered users may post in this forum.

Click here to login