15,747,059 members
Home / Discussions / Algorithms

# Algorithms

 Re: How can I calculate time complexity and compare between given two algorithms? trønderen19-Sep-20 2:43 trønderen 19-Sep-20 2:43
 Re: How can I calculate time complexity and compare between given two algorithms? Richard MacCutchan19-Sep-20 3:01 Richard MacCutchan 19-Sep-20 3:01
 Re: How can I calculate time complexity and compare between given two algorithms? trønderen19-Sep-20 7:06 trønderen 19-Sep-20 7:06
 Re: How can I calculate time complexity and compare between given two algorithms? Richard MacCutchan19-Sep-20 21:05 Richard MacCutchan 19-Sep-20 21:05
 Re: How can I calculate time complexity and compare between given two algorithms? Sandeep Mewara19-Sep-20 0:12 Sandeep Mewara 19-Sep-20 0:12
 Re: How can I calculate time complexity and compare between given two algorithms? Member 1151248619-Sep-20 0:55 Member 11512486 19-Sep-20 0:55
 Re: How can I calculate time complexity and compare between given two algorithms? Gerry Schmitz19-Sep-20 3:00 Gerry Schmitz 19-Sep-20 3:00
 Re: How can I calculate time complexity and compare between given two algorithms? trønderen19-Sep-20 7:03 trønderen 19-Sep-20 7:03
 How can you state as a general conclusion that "the second algorithm takes less time"? Execution times depend on, for algorithm 1, four different input variables (m, n, x, y), and the outcome of four different if-tests, so you may consider p(if-1) .. p(if-4) four additional input variables. Total execution time depends heavily on the resources (mainly CPU) required for evaluating the four different conditions, and for the seven different actions. The execution counts for six of the actions depend on two or three input variables. Algorithm 2 has three input variables (m, n, x) and five tests so p(if-1) .. p(if-5) are input variables. Timing depend on five different evaluation times, seven different actions execution times. Here, too, execution counts for six of seven actions, and two conditions, depend on two or three input variables. An algorithm, as such, is independent of both implementation and the context where it is applied; each step may have an arbitrary interpretation. (The pseudocode description reflects this.) So, e.g. performing another loop iteration may involve a lot more than just incrementing an integer variable and perform a conditional jump back to the top; it could take a lot work to get hold of the next element. So, the loop management itself might be the dominating cost, measured time might be practically independent on all the 'if()' and 'do something'. Total execution times depend heavily on the relative cost of evaluating an 'if()' vs. an action ('do something'). Say, an 'if()' searching a candidate photo for similar ones in a photo archive (a very heavy test), the action simply logs the outcome (very lightweight) - then the number of tests greatly dominate the execution time, almost independent of p(if) probabilities. Or rather: If a test is super-cheap, like looking up the photo's serial number in a list, but the action is like compressing the image, then test outcomes (determined by p(if)) strongly affect execution times. All of this affects benchmark timings, but only them. No matter how dramatic the effects on the timings if you apply the same algorithm in another context - or even port the same program code to another platform with significantly different relative costs: O() is unaffected by relative costs of loop management, tests and actions. Given these considerations, how can we make any reliable statements about algorithm complexity based on execution times measurement measured with a (usually very small) set of combinations of eight explicit input values and a bunch of hidden ones (the relative costs of test/action execution)? Can you claim that algorithm 2 is faster than algorithm 1 for any combination of input variables? Even when considering that y affects algorithm 1 but not algorithm 2? Even when algorithm 1 depends on four different p(if), algorithm 2 on five? If you give me the freedom to set arbitrary cost values (in terms of CPU execution times) for all actions and if() tests, to freely set values for m, n, x and y, and p(if) values, I am quite certain that I could make algorithm 2 significantly slower for given values, but faster for others. Execution times "all depends"! If you set up an O() expression in the input variables, you can, for a given set of input values, estimate (relative) expected execution time for the alternatives. Usually, you simplify the O()-expression, leaving out e.g. constant parts (like step 4 / step 2, independent of input values). If you know that e.g. if tests will always be super-simple, you may leave them out - but you should make that explicit in your presentation of the complexity. It is sort of customary to give O() only by the highest order subexpression(s) (such as m*m*x in algorithm 2, disregarding all p(if)) - but as a main rule, that restricts you complexity analysis to non-extreme values of those parts you have shaven off. If you know the application area, you will usually know the expected range of variation of each value, so you e.g. chop off the x if it varies from 1 to 3 but not if it varies from zero to a billion. In any case: Benchmarks generally covers only a tiny little selection of possible explicit inputs (in particular in an 8-dimentional input space!). Usually, they are based on a large number of hidden (usually unidentified) factors affecting the results. For a specific application of the algorithm, in a specific implementation environment, and with a limited value range for all inputs, the benchmarks may give an indication of expected execution time. But they cannot provide anything comparable to an analytic derived expression for the complexity.
 Re: How can I calculate time complexity and compare between given two algorithms? Gerry Schmitz20-Sep-20 4:52 Gerry Schmitz 20-Sep-20 4:52
 My implementation of Eratosthenes sieve is horribly slow. But why? Member 149328737-Sep-20 22:00 Member 14932873 7-Sep-20 22:00
 Re: My implementation of Eratosthenes sieve is horribly slow. But why? Richard MacCutchan7-Sep-20 22:38 Richard MacCutchan 7-Sep-20 22:38
 Re: My implementation of Eratosthenes sieve is horribly slow. But why? Richard Deeming7-Sep-20 23:59 Richard Deeming 7-Sep-20 23:59
 Re: My implementation of Eratosthenes sieve is horribly slow. But why? Dave Kreskowiak8-Sep-20 6:46 Dave Kreskowiak 8-Sep-20 6:46
 Re: My implementation of Eratosthenes sieve is horribly slow. But why? Richard Andrew x6422-Sep-20 10:36 Richard Andrew x64 22-Sep-20 10:36
 Re: My implementation of Eratosthenes sieve is horribly slow. But why? Dave Kreskowiak22-Sep-20 16:25 Dave Kreskowiak 22-Sep-20 16:25
 Re: My implementation of Eratosthenes sieve is horribly slow. But why? Patrice T18-Sep-20 19:51 Patrice T 18-Sep-20 19:51
 How can I remove alternate words from a sentence? maicart5-Sep-20 22:27 maicart 5-Sep-20 22:27
 Re: How can I remove alternate words from a sentence? Gerry Schmitz6-Sep-20 4:14 Gerry Schmitz 6-Sep-20 4:14
 Re: How can I remove alternate words from a sentence? Richard MacCutchan6-Sep-20 6:13 Richard MacCutchan 6-Sep-20 6:13
 Re: How can I remove alternate words from a sentence? Gerry Schmitz6-Sep-20 6:33 Gerry Schmitz 6-Sep-20 6:33
 Re: How can I remove alternate words from a sentence? Richard MacCutchan6-Sep-20 4:52 Richard MacCutchan 6-Sep-20 4:52
 Re: How can I remove alternate words from a sentence? maicart6-Sep-20 6:23 maicart 6-Sep-20 6:23
 Re: How can I remove alternate words from a sentence? Richard MacCutchan6-Sep-20 6:41 Richard MacCutchan 6-Sep-20 6:41
 Re: How can I remove alternate words from a sentence? Richard Andrew x646-Sep-20 8:04 Richard Andrew x64 6-Sep-20 8:04
 Re: How can I remove alternate words from a sentence? maicart7-Sep-20 1:27 maicart 7-Sep-20 1:27
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Oct-23 10:13 Refresh ᐊ Prev1...78910111213141516 Next ᐅ