Find the two largest elements in an array in n+log (base2)(n) comparisons
You start with the two elements at the start of the array. Compare them, and make a note of the smaller one.
Then, you compare that smaller one to every other element in the array, and each time you find a bigger value, that's your new candidate value.
That's your n comparisons.
Each time, during that set of comparisons, that you DO find a bigger number, you now need to make another comparison, to see if the new number was bigger than BOTH your candidate values, or just the smaller. How many times can you expect to do this? About log(base2)(n) times.
Then, you compare that smaller one to every other element in the array, and each time you find a bigger value, that's your new candidate value.
That's your n comparisons.
Each time, during that set of comparisons, that you DO find a bigger number, you now need to make another comparison, to see if the new number was bigger than BOTH your candidate values, or just the smaller. How many times can you expect to do this? About log(base2)(n) times.
Last edited on
the math is the number of comparisons needed, this is called big-O notation.
take something simple, like the sum of all the values in an array, you have to touch each value once, there are N values (the number of things is always N as a standard understood terminology) so it takes N amount of work.
the math on the log is written funny.
technically, lg is base 2, ln is base e, log is base 10, and there are a few other seldom used ones as well. but in big-o its usually just written log, and the base is usually either not cared about or understood to be 2 (it just happens to usually be 2 for most common algorithms).
you can google big-O notation for some more words on this idea, but what it is asking for is to do this task in that much work or less. Its possible to do in 2*N by checking all the values, then checking them all again ignoring the last one found, for example, but that is not as efficient and they want you to do better than this.
take something simple, like the sum of all the values in an array, you have to touch each value once, there are N values (the number of things is always N as a standard understood terminology) so it takes N amount of work.
the math on the log is written funny.
technically, lg is base 2, ln is base e, log is base 10, and there are a few other seldom used ones as well. but in big-o its usually just written log, and the base is usually either not cared about or understood to be 2 (it just happens to usually be 2 for most common algorithms).
you can google big-O notation for some more words on this idea, but what it is asking for is to do this task in that much work or less. Its possible to do in 2*N by checking all the values, then checking them all again ignoring the last one found, for example, but that is not as efficient and they want you to do better than this.
Topic archived. No new replies allowed.