Asymptotic complexity: Dichotomous research
Sorry in class (I'm in high school) the professor explained this about the asymptotic complexity:
Linear search: "classic" search of an element in a vector;
Dichotomous research: I start from an ordered array and proceed as explained (O (log2 (n)). Notations O, Omega, Theta.
Can someone with a good heart help me understand dichotomous research?
Thank you all.
Linear search: "classic" search of an element in a vector;
Dichotomous research: I start from an ordered array and proceed as explained (O (log2 (n)). Notations O, Omega, Theta.
Can someone with a good heart help me understand dichotomous research?
Thank you all.
I am not sure what you are asking. I have never heard of dichotomous research.
Asymptotic complexity is a generalized way of thinking about how much effort an algorithm takes to solve a given problem in time or space as the number of inputs grows larger. It does not matter what the algorithm is. So long as it does something predicated on some known input then it can be analyzed to require some scalar (unitless) degree of time or space.
“Dichotomous” means having exactly two values. Another word for this is “boolean”. When dealing with dichotomous variables you are getting into statistical stuff.
However, if you are still talking about algorithms — a dichotomous algorithm — you are talking about things that give you a yes or no answer:
• does the set A contain the value x?
• does the program P terminate?
The first is an example of a solvable question, which can be analyzed to terminate in some polynomial time — which is what asymptotic analysis is for.
The second is an example of an NP-hard problem, which cannot be solved or analyzed in any polynomial time. (Sometimes good approximations can be made, such as for the Travelling Salesman Problem, and those approximation algorithms can be analyzed, of course.)
I am not sure how deep into this stuff your teacher is planning to get...
Asymptotic complexity is a generalized way of thinking about how much effort an algorithm takes to solve a given problem in time or space as the number of inputs grows larger. It does not matter what the algorithm is. So long as it does something predicated on some known input then it can be analyzed to require some scalar (unitless) degree of time or space.
“Dichotomous” means having exactly two values. Another word for this is “boolean”. When dealing with dichotomous variables you are getting into statistical stuff.
However, if you are still talking about algorithms — a dichotomous algorithm — you are talking about things that give you a yes or no answer:
• does the set A contain the value x?
• does the program P terminate?
The first is an example of a solvable question, which can be analyzed to terminate in some polynomial time — which is what asymptotic analysis is for.
The second is an example of an NP-hard problem, which cannot be solved or analyzed in any polynomial time. (Sometimes good approximations can be made, such as for the Travelling Salesman Problem, and those approximation algorithms can be analyzed, of course.)
I am not sure how deep into this stuff your teacher is planning to get...
Huh?
Did you translate that correctly?
> Linear search: "classic" search of an element in a vector;
> I start from an ordered array and proceed as explained (O (log2 (n)).
This kind of thing is called a "binary search".
Because you start with things in order, you can examine the mid point and immediately know which half of the array the target value is in. At each step, you eliminate half the possible choices.
Did you translate that correctly?
> Linear search: "classic" search of an element in a vector;
> I start from an ordered array and proceed as explained (O (log2 (n)).
This kind of thing is called a "binary search".
Because you start with things in order, you can examine the mid point and immediately know which half of the array the target value is in. At each step, you eliminate half the possible choices.
I think OP is comparing the two searches: O(log2n) is a binary search complexity, which is waaay better than an O(n) linear search. Notice the semicolon between his two statements.
[edit]
Perhaps he is using “dichotomous research” to mean “binary search”?
[edit]
Perhaps he is using “dichotomous research” to mean “binary search”?
Last edited on
are you asking about the notation and how to read/write it, or how to get it from an algorithm, now sure exactly what you want to know?
binary search works by cutting in half every time. if you have some numbers in ascending order:
1 2 3 4 5 6 7 8 9 10
and you want to know if 9 is in there?
linear search just looks at 1, 2, 3, 4,... until it finds 9. it has to examine 9 values to find it.
binary search looks at the middle value:
is 9 > 5? yes.
it then discards half the data and asks
is 9 in
5 6 7 8 9 10
it looks again at the middle value:
is 9 > 8? yes
it discards half and again
is 9 in
8 9 10
it looks at middle value (its 9, success, stop). it found it in far less than 9 tries.
the bigger the array, the more astounding this can be; for around 1 million it can find it in about 20 tries, whereas linear would take about 1/2 a million looks on the average!!
the trick is seeing that when you cut something in half every time, that is a log based complexity. how many times do you need to take half until you know something is not there? it turns out to be lg(size)+1. All I know to tell you on that is that you will soon see 99% of the common O() patterns and it will quickly come naturally to you. There are < 10 common patterns to know for almost all code.
O(1)
O(N)
O(N*N) (N*N*N) and very rare higher powers
O(log(n))
O(n*log(n))
O(n!) rare, and usually not something you would use.
O(constant to nth power) less rare, but not used. These large ones are too slow for practical code.
I think that is most of them.
binary search works by cutting in half every time. if you have some numbers in ascending order:
1 2 3 4 5 6 7 8 9 10
and you want to know if 9 is in there?
linear search just looks at 1, 2, 3, 4,... until it finds 9. it has to examine 9 values to find it.
binary search looks at the middle value:
is 9 > 5? yes.
it then discards half the data and asks
is 9 in
5 6 7 8 9 10
it looks again at the middle value:
is 9 > 8? yes
it discards half and again
is 9 in
8 9 10
it looks at middle value (its 9, success, stop). it found it in far less than 9 tries.
the bigger the array, the more astounding this can be; for around 1 million it can find it in about 20 tries, whereas linear would take about 1/2 a million looks on the average!!
the trick is seeing that when you cut something in half every time, that is a log based complexity. how many times do you need to take half until you know something is not there? it turns out to be lg(size)+1. All I know to tell you on that is that you will soon see 99% of the common O() patterns and it will quickly come naturally to you. There are < 10 common patterns to know for almost all code.
O(1)
O(N)
O(N*N) (N*N*N) and very rare higher powers
O(log(n))
O(n*log(n))
O(n!) rare, and usually not something you would use.
O(constant to nth power) less rare, but not used. These large ones are too slow for practical code.
I think that is most of them.
Last edited on
Topic archived. No new replies allowed.