• Advertisement

Archived

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

Determining O-notation

This topic is 5095 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
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 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
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

Share this post


Link to post
Share on other sites
It's like insertion sort: all humans use insertion sort for manual sorting of papers,etc, because time to insert are constant,and time complexity are n*log(n) .

But for computer,insertion sort in simplest form are o(n^2) or if one doing it like using binary search,even more, o(n^2 * log(n))

[edited by - Dmytry on March 8, 2004 1:09:51 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Dmytry
It''s like insertion sort: all humans use insertion sort for manual sorting of papers,etc, because time to insert are constant,and time complexity are n*log(n) .

But for computer,insertion sort in simplest form are o(n^2) or if one doing it like using binary search,even more, o(n^2 * log(n))

[edited by - Dmytry on March 8, 2004 1:09:51 PM]


Why would someone use a more complex version of insertion sort that gives them worse running time? And also don''t forget that best case insertion sort runs O(n) and makes it the fastest sorting algorithm in those cases.

Share this post


Link to post
Share on other sites
quote:
Original post by shmoove
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).

Unfortunately, the arithmetic is not that straight-forward.

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

Since A(n) is 2, we can write

D(n) = if n = 0 then 2 else 2*D(n/2)+2;;

D(2) = 2*D(1)+2
D(4) = 2*D(2)+2 = 4*D(1)+6
D(8) = 2*D(4)+2 = 8*D(1)+14
...
D(2^k) = 2*D(2^(k-1))+2 = (2^k)*D(1)+2^(k+1)-2 = (D(1)+2)*(2^k)-2

So for powers of 2, D(n) = (D(1)+2)*n-2, which is not O(log n). It is O(n) though.

Share this post


Link to post
Share on other sites
quote:
Original post by YoshiN
quote:
Original post by Dmytry
It's like insertion sort: all humans use insertion sort for manual sorting of papers,etc, because time to insert are constant,and time complexity are n*log(n) .

But for computer,insertion sort in simplest form are o(n^2) or if one doing it like using binary search,even more, o(n^2 * log(n))

[edited by - Dmytry on March 8, 2004 1:09:51 PM]


Why would someone use a more complex version of insertion sort that gives them worse running time? And also don't forget that best case insertion sort runs O(n) and makes it the fastest sorting algorithm in those cases.


If data sometimes are already sorted(insertion sort in o(n)),one should first check if it's sorted,and then use quicksort,heap sort,advanced insertion sort,or something else.

Ops,there's mistake,that's not O(n^2*log(n)),but O(n^2+log(n)),i mean doing binary search first,and then doing insertion.
And second version are faster if compare isn't very cheap.
(second version are very similar to manual sorting,when sorting papers,you do something like binary search in sorted papers , then insertion)

Also,if one uses "algorithms instead of hand-written loops" (see "general programming" forum) , one may not know if insert are cheap or not.

[edited by - Dmytry on March 8, 2004 4:38:18 PM]

Share this post


Link to post
Share on other sites
D(n) = if n = 0 then 2 else 2*D(n/2)+2
Let n = 2^i
D(2^i) = if 2^i=0 then 2 else 2*D(2^i/2)+2
therefore
C(i) = if i = -infinity then 2 else 2*C(i-1)+2
is the same recurrance for powers of 2
c(i)-2*C(i-1)=2
(x-2)(x-1)=0 is the characteristic polynomial for this reccurance
x=2,1
C(i)=c1*2^i+c2*1^i=c1*2^i+c2
D(n)=c1*2^log(n)+c2
D(n)=c1*n+c2

We know c2 has to be 2 but you can't really solve for c1 because n/2 will never equal zero unless n starts off as 0.


[edited by - O_o on March 8, 2004 5:05:04 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by alvaro
So for powers of 2, D(n) = (D(1)+2)*n-2, which is not O(log n). It is O(n) though.

Maybe I misunderstand what you say here, but ToohrVyk was talking about the number of operations in the algorithm, not the size of D(n).

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
quote:
Original post by alvaro
So for powers of 2, D(n) = (D(1)+2)*n-2, which is not O(log n). It is O(n) though.

Maybe I misunderstand what you say here, but ToohrVyk was talking about the number of operations in the algorithm, not the size of D(n).



In ToohrVyk''s post, D(n) represents the number of operations that an algorithm takes to execute.

Share this post


Link to post
Share on other sites

  • Advertisement