• ### What is your GameDev Story?

#### Archived

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

# Determining O-notation

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

## 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 on other sites
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 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 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 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 on other sites
Yeah, I mean''t Omega, not sigma. I should really hold up on the southern comfort..

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

##### 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 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 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 on other sites
The "2*" part is O(1) (just like the + A(n)) so it doesn''t make a difference and D(n) is O(log n).

shmoove

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
634150
• Total Posts
3015827
×