How to estimate the time complexity for insertion sort by measuring the gradient of a log-log plot?

Question

This is the graph which I am expected to analyze. I have to find the gradient (slope) and from that I am expected to deduce the time complexity.

I have found that the slope is equal to 1,91. If that is true what else should I do?

Answer 1

Quotient of logarithms is approximately 2. What does it mean when removing the logarithms?

log(T(n)) / log(n) = 2
log(T(n)) = 2 * log(n)
log(T(n)) = log(n²)
T(n) = n²

T(n) denotes algorithm’s time complexity. Of course we are talking in asymptotic terms, i.e. using Big O notation we say that

T(n) ∈ O(n²).

You measured the value 2 for large inputs and you are assuming it will remain the same even for all bigger ones.

You can read more at a page by one of the tutors at University of Toronto. It uses basic calculus to explain how it works. Still, the idea behind all this is that logarithms make multiplicative constants from constant exponents and additive constants from multiplicative constants.

Also regarding interpretation of the plot, a similar question popped up here on Stack Overflow recently: Log-log plot/graph of algorithm time complexity

But note that this is really just an estimation of time complexity. You cannot prove time complexity of an algorithm by just running it on a finite set of inputs. This method can give you a good guess on what to try to prove using analysis of the algorithm, though.