Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Determining O-notation

This topic is 5186 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Could someone please explain to me how to determine the O-notation for any particular algorithm or function? If you could write a simple "Hello world" example for O(n), O(n^2), etc, that would be wonderful. I want to understand how to look at some simple code and determine what the value would be. If the examples could be kept to the most simplistic representation possible, that''d be great. Example I think is correct for O(n): ... for(int i = 0; i < 100; ++i) { cout << i << endl; } ... Is that correct? Other examples or links to examples for the rest of the O-notation values would be helpful. Thank you very much for any help.

Share this post


Link to post
Share on other sites
Advertisement
You should replace ''100'' with ''n''.

It''s looks like O(n*log n) :-)

O(n*(a+log n))
where a depends to "cout" implementation

Number of chars to write are proportional to log(n),and number of writes are proportional to n



...

Share this post


Link to post
Share on other sites
You simply count the number of operations to perform a simple task. Some examples are :

A(n) = 1 + 1;
is O(1)

B(n) = for i = 0 to n do A(n) done;;
is O(n)

C(n) = for i = 0 to n do B(n) done;;
is O(n²)

D(n) = if n = 0 then A(n) else 2*D(n/2)+A(n);;
is O(log(n))

E(n) = if n = 0 then A(n) else 2*D(n/2)+B(n);;
is O(n log(n))

A is always O(1).
B & C 's complexities are computed by summing the number of operations (in the first case, n, in the second case, 1+2+..+n=n(n+1)/2 )
D & E's complexities are computed using n = 2^k, so k = log2(n), hence the log.

Victor Nicollet, INT13 game programmer



[edited by - ToohrVyk on March 7, 2004 3:42:59 PM]

[edited by - ToohrVyk on March 7, 2004 3:43:22 PM]

Share this post


Link to post
Share on other sites
You might want to look up theta and sigma ( not generally used, but still nice to know ) notation aswell, and Master Theorem.

You have to remember that you''re unique, just like everybody else.

Share this post


Link to post
Share on other sites
Big Theta notation is the most useful because you can just say that pretty much every algorithm is in O(n^n) which is pretty useless =p. Also it's O-notation, Theta-notation and Omega-notation. Everything is in Omega(1) as well.

[edited by - O_o on March 7, 2004 4:03:41 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Dmytry
You should replace '100' with 'n'.

It's looks like O(n*log n) :-)

O(n*(a+log n))
where a depends to "cout" implementation

Number of chars to write are proportional to log(n),and number of writes are proportional to n

For simplicity's sake, I'm sure you can assume cout runs in constant time regardless of 'n' and stick with O(n).

[edited by - Zipster on March 7, 2004 6:14:53 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Zipster
For simplicity''s sake, I''m sure you can assume cout runs in constant time regardless of ''n'' and stick with O(n).


Dmytry made a good point here. It is important to know that things that look atomic in C++ may actually involve some sub-algorithm. For instance,

for(int i=0;i<strlen(s);i++)
if(!isalpha(s[i]))
break;

may look O(n), where n is the lenght of the string s. But in fact it''s O(n^2) because every call to strlen is O(n) itself.

Share this post


Link to post
Share on other sites
quote:
Original post by ToohrVyk
A(n) = 1 + 1;
is O(1)

[...]

D(n) = if n = 0 then A(n) else 2*D(n/2)+A(n);;
is O(log(n))



I think that''s wrong. If you remove the "2*" part, it would be true. As stated, it''s D(n)=O(n).

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!