
Ryan McGuire wrote:As far as the math goes, I'm going to point at my first post in this thread: Use the known data set size and time to determine a coefficient, and then use that coefficient to estimate the time for the larger data set size.
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
I hate signatures!
Piet Souris wrote:Or one could pay some more attention to what has been replied sofar.
Since 0 < log (2) / log (N) < 1, we get a ratio that is between 2 and 4.
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
Junilu Lacar wrote:N log N is not a linear function wheres calculating for a coefficient like that assumes that it is.
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
If you want nice clear terms that explain what they mean without your having to look in several dictionaries all giving slightly different definitions, look no further!Junilu Lacar wrote:. . . quasilinear or linearithmic . . .
Of course that is a valid calculation.calculating a coefficient the way Ryan showed is valid after all.
Campbell Ritchie wrote:Of course that is a valid calculation.
Ryan McGuire wrote:How to do these in general:
1. Create an equation that sets the known time equal to an unknown coefficient times the big O expression with the known value for N substitutes in.
2. Solve that for the unknown coefficient.
3. Use that with the other known value for N to get the (reasonable estimate of) the time for that N value.
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
I only checked that one calculation. For quadratic complexity, I would calculate 3 × 1000² ÷ 500², which should come to 12.Junilu Lacar wrote:. . . incorrect for the other types of curves that are nonlinear. . . .
Campbell Ritchie wrote:For quadratic complexity, I would calculate 3 × 1000² ÷ 500², which should come to 12.
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
I hate signatures!
See this RO thread and here. You need to learn a few Unicode numbers; you will find superscripts and subscripts here. By the way, superscript 1 is ¹ not what I posted before. You can also try ¹ = ¹.Piet Souris wrote:. . . nice sub and superscripts . . .
Junilu Lacar wrote:But that kind of begs the question "Why try to come up with all these other approaches for this exercise when the 2nd column already tells you what to do?"
That part is correct for the figures given.Ryan McGuire wrote:. . . 2x < work < 4x . . .
Agree that part is at best confusing.. . . "increase by 1" for the O(logN) . . .
At this point, you might start to move out of Big O notation; maybe 50000 executions will fill the available heap space and require multiple GC runs, causing space complexity to become its limiting factor. Repeated String concatenation is rather like that, though the Java9+ performance is much faster than in earlier versions.. . . 3 ms to complete for a data set of N=500, how long would you expect it to take for an N=50,000 . . .
Campbell Ritchie wrote:
At this point, you might start to move out of Big O notation; maybe 50000 executions will fill the available heap space and require multiple GC runs, causing space complexity to become its limiting factor. Repeated String concatenation is rather like that, though the Java9+ performance is much faster than in earlier versions.. . . 3 ms to complete for a data set of N=500, how long would you expect it to take for an N=50,000 . . .
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
How to Ask Questions  How to Answer Questions  Format Your Code
Roses are red, violets are blue. Some poems rhyme and some don't. And some poems are a tiny ad.
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
