Worst case running time (Big O)

Question

Hi every one. I have this question, and I don't know how to solve it, because I don't understand it. :(

The question is:

Programs A and B are analyzed and are found to have worst case running times no greater than 150n log n and n², respectively. Answer the following questions:

i) Which program has the better guarantee on the running time for large values of n (n > 10000)?

ii) Which program has the better guarantee on the running time for small values of n (n < 100)?

Can any one help me and explain it for me?

Answer 1

You're given two formulae and two different values of n to plug into them. Then you're asked which formula has the larger value in each case.

I suggest plugging the two values of n into the formulae and figuring out which is larger in each case.

Answer 2

Worst case run time means the absolute longest the program will run given an input of length n. So the two formulas you were given are their worst case run times. Mathematically, both formulas behave differently at different sizes of n. Experiment with the size of n and see how they respond. That will help you understand and find your answers.

Answer 3

See yourself at WolframAlpha. The point where the worst cases are equal is circa at 1042. That should answer your question.

Answer 4

If the actual question is O(n^2), ii is a trick question.

In Big-O notation, you can drop constants, so O(10000n^2) is the same as O(n^2). If you haven't removed the O() from the question, then just fill in the equations, that shouldn't be hard to work out.

Answer 5

Have you looked at a graph of the two complexity functions?