Click here to Skip to main content
15,434,755 members
Home / Discussions / Algorithms
   

Algorithms

 
AnswerRe: How can I calculate time complexity and compare between given two algorithms? Pin
trønderen19-Sep-20 2:43
Membertrønderen19-Sep-20 2:43 
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
Richard MacCutchan19-Sep-20 3:01
mveRichard MacCutchan19-Sep-20 3:01 
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
trønderen19-Sep-20 7:06
Membertrønderen19-Sep-20 7:06 
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
Richard MacCutchan19-Sep-20 21:05
mveRichard MacCutchan19-Sep-20 21:05 
AnswerRe: How can I calculate time complexity and compare between given two algorithms? Pin
Sandeep Mewara19-Sep-20 0:12
mveSandeep Mewara19-Sep-20 0:12 
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
Member 1151248619-Sep-20 0:55
MemberMember 1151248619-Sep-20 0:55 
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
Gerry Schmitz19-Sep-20 3:00
mveGerry Schmitz19-Sep-20 3:00 
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
trønderen19-Sep-20 7:03
Membertrønderen19-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.
GeneralRe: How can I calculate time complexity and compare between given two algorithms? Pin
Gerry Schmitz20-Sep-20 4:52
mveGerry Schmitz20-Sep-20 4:52 
QuestionMy implementation of Eratosthenes sieve is horribly slow. But why? Pin
Member 149328737-Sep-20 22:00
MemberMember 149328737-Sep-20 22:00 
AnswerRe: My implementation of Eratosthenes sieve is horribly slow. But why? Pin
Richard MacCutchan7-Sep-20 22:38
mveRichard MacCutchan7-Sep-20 22:38 
GeneralRe: My implementation of Eratosthenes sieve is horribly slow. But why? Pin
Richard Deeming7-Sep-20 23:59
mveRichard Deeming7-Sep-20 23:59 
AnswerRe: My implementation of Eratosthenes sieve is horribly slow. But why? Pin
Dave Kreskowiak8-Sep-20 6:46
mveDave Kreskowiak8-Sep-20 6:46 
GeneralRe: My implementation of Eratosthenes sieve is horribly slow. But why? Pin
Richard Andrew x6422-Sep-20 10:36
professionalRichard Andrew x6422-Sep-20 10:36 
GeneralRe: My implementation of Eratosthenes sieve is horribly slow. But why? Pin
Dave Kreskowiak22-Sep-20 16:25
mveDave Kreskowiak22-Sep-20 16:25 
AnswerRe: My implementation of Eratosthenes sieve is horribly slow. But why? Pin
Patrice T18-Sep-20 19:51
mvePatrice T18-Sep-20 19:51 
QuestionHow can I remove alternate words from a sentence? Pin
maicart5-Sep-20 22:27
Membermaicart5-Sep-20 22:27 
AnswerRe: How can I remove alternate words from a sentence? Pin
Gerry Schmitz6-Sep-20 4:14
mveGerry Schmitz6-Sep-20 4:14 
GeneralRe: How can I remove alternate words from a sentence? Pin
Richard MacCutchan6-Sep-20 6:13
mveRichard MacCutchan6-Sep-20 6:13 
GeneralRe: How can I remove alternate words from a sentence? Pin
Gerry Schmitz6-Sep-20 6:33
mveGerry Schmitz6-Sep-20 6:33 
AnswerRe: How can I remove alternate words from a sentence? Pin
Richard MacCutchan6-Sep-20 4:52
mveRichard MacCutchan6-Sep-20 4:52 
GeneralRe: How can I remove alternate words from a sentence? Pin
maicart6-Sep-20 6:23
Membermaicart6-Sep-20 6:23 
GeneralRe: How can I remove alternate words from a sentence? Pin
Richard MacCutchan6-Sep-20 6:41
mveRichard MacCutchan6-Sep-20 6:41 
GeneralRe: How can I remove alternate words from a sentence? Pin
Richard Andrew x646-Sep-20 8:04
professionalRichard Andrew x646-Sep-20 8:04 
GeneralRe: How can I remove alternate words from a sentence? Pin
maicart7-Sep-20 1:27
Membermaicart7-Sep-20 1:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.