CODEWITHSUNDEEP
calgorithmdata-structures
P.P
P.P

Reputation: 121397

Graphs for Big O notation

I wonder if there's any tool/website where I can plot some run times as graphs. Because, the asymptotic notation is often not what I wanted i.e. Don't want to ignore constants.

For example, suppose I have two notations, like:

1) O = (n * log n).
2) O = (n * log n * log n)/5.

It's obvious that 1st one is asymptotically better. But what I want to see how they perform and at which point the second one starts to become better.

A graphical notation where I can enter different equations and plot them them to see how they vary would be greatly useful for this purpose. In my search I found this site where they have some plots. I am looking for something similar but I also want to input my equations to plot to analyse the performance for various 'n' values.

Upvotes: 0

Views: 5366

Answers (3)

Karoly Horvath
Karoly Horvath

Reputation: 96266

If you want to see how they perform then you have to implement the algorithms and execute them on various graph. Modern processors with memory locality and cache misses make it really hard to come up with an equation that gives you a reasonable estimation.

I can guarantee you that oyu won't measure what you would expect.

Upvotes: 0

lucian.pantelimon
lucian.pantelimon

Reputation: 3669

Would this or this help?

If you use a 3d grapher, you can use the other dimension (say y) as a constant replacement. This way you would be able to interpret results as:

when y is greater than 5, n*log(n)*log(n)/y is better than n*log(n) starting from n = (actual value)

Also, you can ignore the 3rd dimension. Or use it if you have a complexity depending on 2 variables.

Just input the difference between the complexities. In this case, ignoring the 3rd dimension and considering log(x) = ln(x), the equation is:

z = x*ln(x) - x*ln(x)*ln(x)/5

An you can interpret that as x*ln(x) is more efficient when z is negative.

Upvotes: 1

Reed Copsey
Reed Copsey

Reputation: 564441

As soon as you stop "ignoring constants", you're no longer graphing "Big O" notation, but just performing a standard XY plot. As such, any graphing program, even online graphing calculators, would let you display this, just replace "n" for "X" and you'll get the proper graph.

Upvotes: 5

Related Questions