0

I have a problem that my professor gave us:

Algorithms A and B spend exactly TA(n) = 0.1n^2log10(n) and TB(n) = 2.5n^2 microseconds, respectively, for a problem of size n. Choose the algorithm, which is better in the Big-Oh sense, and find out a problem size n0 such that for any larger size n > n0 the chosen algorithm outperforms the other. If your problems are of the size n ≤ 10^9, which algorithm will you recommend to use?

At first, I thought algorithm A would be better in the Big-Oh sense, but his answer says A is better. My reasoning for A being better is that it grows slower than B. Am I correct or is my professor correct?

Here's his answer:

In the Big-Oh sense, the algorithm B is better. It outperforms the algorithm A when TB(n) ≤ TA(n), that is, when 2.5n^2 ≤ 0.1n^2log10(n). This inequality reduces to log10(n) ≥ 25, or n ≥ n0 = 1025. If n≤ 10^9, the algorithm of choice is A

Is he correct or am I correct?

Improve this question
1
  • The professor proves that TB(n) grows slower than TA(n), which contradicts your assertion that "A grows slower than B". What other argument would you like to see? Commented Feb 12, 2017 at 23:17

1 Answer 1

Reset to default
2

B is better in big-o terms because it takes time proportional to n squared, but A is proportional to n squared times log n which is bigger. So for large enough values of n B will be faster.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.