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]
Determining O-notation
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.
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.
quote:Original post by YoshiNquote: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]
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]
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]
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).
quote:Original post by Anonymous Posterquote: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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
