Big O: What is the relationship between O(log(n)) with real time

Question

I've calculated the real time in millisecond for my algo. I've plotted a graph comparing the actual time taken by my algorithm in Milli-Seconds(y-axis) to 'n'(x-axis) where n is the number of nodes in the tree I'm working on.

How do I relate this graph to O(log(n)) if my algorithm should ideally have a O(log(n)) complexity.

The question is that in a graph with y axis as the time in milliseconds and x axis as 'n'. Can we compare the complexity of my algo with a graph log(n). @specializt — Identity1, Jun 02 '15 at 09:36

Daniel Jour · Answer 1 · 2015-06-02T10:10:36.723

3

Assuming your algorithm is in O(log n) the graphs should make for a nice comparison. But don't plot log n, you need k * log n + c for some constants k and c.

The constant k describes the duration of a single step of your algorithm, whereas c summaries all constant (initialization) cost.

Depending on what you want to achieve and your algorithm / implementation you might see effects like processor cache misses, garbage collection or similar stuff with increasing n.

edited Jun 02 '15 at 10:10

answered Jun 02 '15 at 09:59

Daniel Jour

15,896
2
36
63

Yeah! Some runs with a high 'n' seem to look erroneous @Daniel Jour – Identity1 Jun 02 '15 at 10:31
What about a graph of log(n) Vs 'time taken in Milliseconds' does it provide any insight? – Identity1 Jun 02 '15 at 10:33
@Identity1 my answer concludes that graph as well – AvidLearner Jun 02 '15 at 12:54

AvidLearner · Answer 2 · 2015-06-02T12:56:39.637

1

In case you can save n,log(n),runtime(n):

enter image description here

You can use 3 visualization approaches (I used Excel since it is easy and fast):

Draw a QQ-plot between log(n) and your run time:

This figure shows you the difference between the 'Theoretical' run time function and the 'Empirical' run time function. A straight line (or close) implies that they are close.

Draw two plots on the same graph: the horizontal axes is n, and the two functions are log(n) and the run time you obtained for each n:

enter image description here

The third analysis is the statistical approach: plot a graph where the horizontal axis is n, and the vertical axes is runtime(n). Now, add a logarithmic trend line and Rsquare.

enter image description here

The trend line can give you the best a,b where runtime(n)=a*log(n)+b . The correlation between the runtime and log(n) is better as Rsquare gets higher.

edited Jun 02 '15 at 12:56

answered Jun 02 '15 at 12:43

AvidLearner

4,123
5
35
48

Can't see the images @OBP – Identity1 Jun 03 '15 at 03:53
@Identity1 something changed? – AvidLearner Jun 03 '15 at 13:48
No buddy I guess it's some isse with my network @OBP – Identity1 Jun 04 '15 at 06:02
It really demonstrate the techniques you can use, try view it with from another computer... Waiting for you to comment on it – AvidLearner Jun 04 '15 at 09:16
Yeah buddy! I'll read more about it soon...I'll get this issue fixed as soon as I'm free. Thanks for the reply though, looks worth a try (Upvoted!) – Identity1 Jun 04 '15 at 09:43
@Identity1 So, did you see the graphs? did it help? feel free to accept :) – AvidLearner Jun 15 '15 at 19:12

Big O: What is the relationship between O(log(n)) with real time

2 Answers2