Order of Magnitude (Big O) of Algorithms?

Question

A tennis tournament has n players. Each match involves 2 players. Each match will have a winner who advances to the next round and a loser who is eliminated. What is the total number of matches that will determine the final winner? (Already answered this part)

Algorithm A -The number of matches in the first round is n divided by 2 if n is and even number and (n-1) divided by 2 if n is odd. There will be either n divided by 2 or (n+1) divided by 2 players who advance to the next round. This process is repeated until there is a single championship match. The answer to the question is the sum of the number of matches in each round.
Algorithm B - Since each match produces a loser, there must be as many matches as losers.

What I want to know is, what's the order of magnitude of algorithms A and B? Thanks!

And also, are there any good sites with practice problems like these? Thanks again!

Answer 1

Algorithm B is easy -- just one operation is needed, thus O(1).

Algorithm A, you may code as:

For each round {
Calculate the number of matches in round, and accumulate
}

If the inner calculation can be regarded as a fundamental operation, or implies at most a constant number of fundamental operations, then it is O(log n), as it is the order of the number of rounds. I think that is the answer they require, but to comment on the previous answer I consider the next possibility.

If the fundamental operation is each match, or each match implies at most a constant number of fundamental operations (eg. checking who won the match, filling in the queue, deleting the match, etc.), then I don't agree with the person that says that it is O(n * log n), because the number of matches decreases exponentially with each round. If you have to go through each player to see if they play in that round or not, then yes, it is O(n * log n), but if this is avoided by having a queue of matches for example, then you have no more than k*n + k*n/2 + k*n/4 + ... + k operations, which are equal to 2k*n, with order O(n). It is reasonable, as you are going through each match only once, and not doing other repeated operations (if you don't go through each player every round, as explained before).

Answer 2

algorithm B: O(1) ... you know the answer from the start, i.e. n-1. Thus only one operation.

algorithm A: O(n log n) ... since you are going through each match to determine the next round. Remember that constants don't mean a thing in big O stuff.

Answer 3

i think of you will have misunderstood some undertaking whilst listening to related to the massive Bang theory. the massive Bang theory states that each undertaking is created from a tiny component, smaller than an atom (now not an Atom). even via fact the bang exploded, (and don't ask the placement this have been given right here from via fact no person knows of in any appreciate), they say that via fact it sped up Subatomic debris formed (one in each of those count quantity quantity quantity). those have been smaller than atoms - be wakeful that there have been not any atoms perfect contained interior the commencing up of the Universe till finally 380,000 years after - and that they have got been chaotic. Very, very chaotic. As in, that that they had bypass from one place to the quite a few, some ought to prefer to seem on an comparable place and it become all genuinely mayhem. After wards - please understand if I do get information incorrect, i don't prefer you to quote me, this is unquestionably what I surely have heard - count quantity quantity quantity and anti-count quantity quantity quantity annihilated one yet yet another in, say, a conflict. After this 'conflict' count quantity quantity quantity had one. Gravity, on the prompt, become rather stable and now looks very susceptible. carry a chain of keys and drop it to the floor, it is gravity. besides the fact that, carry a magnet and the magnet will attraction to the keys and Gravity loses - unusual! After 380,000 years or so atoms began to form which created Galaxies, stars, planets, moon and greater. and that's rather description. yet do not quote me on each and each and all the documents!

Answer 4

you know the answer anyway