[hashom]

hello guys

i have exam after 1 week and i need help in this question

Assume that we have two algorithms for solving one specific algorithm. The first algorithm (A) takes time n, while algorithm ( takes time 3lg n+5. When should we choose algorithm A, and when should we choose algorithm B?

[BetaWar]

If you graph the two algorithms against each other you can see exactly where one algorithm is better (closer to 0 on the y) than the other:
http://www.wolframal...8427ea9nbpa02ht

[macosxnerd101]

If algorithm A takes time n, then it is O(n). Similarly, algorithm B is O(log(n)). Which is the dominant complexity class?

[Skydiver]

This is where I jump in again where the complexity only tells you a little bit of the story. It tells you how the algorithms will behave as the inputs grow, but it is the actual graphs that will give you the real data.

Let's say that you are comparing an O(n) algorithm vs. an O(n²). On the surface it looks like the O(n) algorithm looks much better. But what if each step of the O(n) algorithm takes 1 year to complete, while each step of the O(n²) requires a microsecond, will you still pick the O(n) algorithm?

[macosxnerd101]

That's a good point. A realistic example of this would be to use Mergesort on arrays, but switch to insertion sort for the smaller cases (arrays with <= 10 elements), since Insertion Sort does better for smaller data sets.