0
$\begingroup$

I'm evaluating two different algorithms to choose one for my implementation, they just do calculations on top of arrays, get some input of $n$ elements, and produce some output of $m$ elements, and I'm looking for an opinion about which one will scale better.

The output they provide given the input is exactly the same on both cases, the computation time for the second is slightly better, maybe a 20%...

As I have the code from both, I have been able to get some counts out of the main loop, where the processing happens (they are iterative).

The first Algorithm behavior reminds me a lot merge sort, for a input $n$, every iteration just process half of the elements, so for $n=4000$ each iteration process half of the elements until there is no more $i_1=2000,i_2=1000,i_3=500,...,i_x=1$

The second Algorithm is just linear, I did the same count thing, and with input $n=4000$, looks like it just process $\approx n/c$ (some $c$) elements per iteration, so $i_1=266,i_2=266,i_3=266,...,i_x=266$

(They do not depend on the numerical values in the input)

Which one will you choose?

Improve this question
$\endgroup$
7
  • $\begingroup$ If you want us to compare the algorithm explain them. Here are we talking up to 4000? $\endgroup$
    – kelalaka
    Oct 12, 2018 at 21:15
  • $\begingroup$ Hi @kelalaka that is the test I run to get the info, but could be up to 16M elements in a single array $\endgroup$
    – John Seppard
    Oct 12, 2018 at 23:57
  • $\begingroup$ I improved just a bit the question as well $\endgroup$
    – John Seppard
    Oct 12, 2018 at 23:59
  • 1
    $\begingroup$ @JohnSeppard, it looks like you are asking people to help you make a choice based on the incomplete information you provided. Can you post the algorithm as well as some typical input somewhere such as pastbin.com? $\endgroup$
    – John L.
    Oct 13, 2018 at 1:05
  • 1
    $\begingroup$ Do you have any difficulty posting your algorithms and some typical data? The best way for people to decide for you is letting them have as much information as you have. For me, I would like to take a look at the algorithms at least. The distribution pattern of the data is important, too. Knowing what is happening at $n=4000$ is not enough to predict how they will behave at 10 million. $\endgroup$
    – John L.
    Oct 13, 2018 at 1:24

1 Answer 1

Reset to default
1
$\begingroup$

You are not looking for asymptotic behaviour, but for actual runtime for rather large n; you determine how large.

You can either analyse both algorithms, and estimate what their run times will be, or much easier, you can measure it. You have to be very careful if you do this with an optimising compiler, because they tend to throw away operations if they can prove they are not actually used. But done carefully, this will give you the actual numbers.

Draw some graph showing the runtime depending on N. And be aware that different processors or different compilers can produce rather different results. Also be aware that if the time "jumps" for certain sizes of n, lets say 50n nanoseconds if n < 10,000, 100n nanoseconds if n < 1,000,000 and 200n nanoseconds if n > 1,000,000 then your time may be depending on memory access, and you can often improve time significantly be re-arranging operations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I realize the question is ill-formed and should be deleted, I'll accept your answer because is one approach, weak but probably works with limitations as you pointed out, and I'll let the moderators decide if this question and answer makes sense for cs. thanks! $\endgroup$
    – John Seppard
    Oct 13, 2018 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.