Identifying which Algorithm is which and explaining the running times

Question

For a given problem with input size n, Algorithms A,B,C are executed. In terms of running time, one of the algorithms is O(n), one O(nlogn) and one O(n^2). Some measured running times of these algorithms are given below

                            Input Size
                    512         1024            2048

            A        70          134             262 
            B        135         517             2053
            C        42          86              182

Identify which algorithm is which and explain the observed running times. Which algorithm would you select for different values of n

Please help me with the above question. Thanks

Answer 1

Graph the performance of the three algorithms - the time complexity will then become obvious.

Answer 2

Look at the quotients of the input sizes and the computing times.

Answer 3

Make sure you understand the terms nlogn, n^2 and n. Consider plotting this functions to understand the relationship between input and their output. The answer will be obvious if you understand these relationships.

Answer 4

Draw the graphs of the 3 dataset. Compare with the growth rate of the graphs for n, nlogn... You will see.

Answer 5

This is what their plot would look like

Now if you understand what time complexity implies and how the graphs of n, n² and nlogn would look like, it shouldn't be difficult.

Answer 6

Often times, I have found that the easiest way to compare complexities was to "normalize" the results.

Input Size:      1       2      4
Algorithm A:     1      1.91   3.74
Algorithm C:     1      2.04   4.33
Algorithm B:     1      3.82  15.21

This table is simply obtained by divising each line by its minimum (the first element in this case).

I have then re-ordered the lines from the slow-growing one to the fast-growing one: can you guess the complexity of each of the algorithms ?

PS: the cheat sheet for n log n, just to verify the approximations

Input Size       Time
n                n log n
2*n              2 * n * (log n + log 2)
4*n              4 * n * (log n + 2 * log 2)

Answer 7

This question leaves me surprised: that there are teachers who ask such kind of bogus and misleading questions.

1) Did the question really talk about O(n), O(nlogn), O(n^2) when they really mean Theta(n), Theta(nlogn) and Theta(n^2)?

2)

Just three data points (or 9 total) is not sufficient to distinguish which is which.

We can choose the appropriate constants so that A,B,C could be any of the three we want.