Hi Euldji, there is a way to compare various algorithm, is using their complexity.

The complexity of an anlgorithm can be stated in different ways:

1.- Temporal complexity

2.- Spatial complexity

Now, the complexity can be calculated in two ways:

1.- Theoretical

2.- Empirical

In the case of theoretical way, you need to calculate a bond of steps, using the big O notation for the worst case.

For your situation, i think that you need a way to measure the empirical time of both excecutable program. In linux, you cna write in a console the following command:

>> time

and when program finish, you will have the execution time.

I hope this will help you.

@Rafael : Then you concur that it would be absurd to compare between complex algorithms based on the big O notation, and the empirical way would be the best.

I am following the same idea, the real challenge to me is to set a Glass Box suite to compare between my algorithms and the previously existed ones.

The real pain in the neck is that I don't have the source code for the most important programs I am possessing right now.

Thank you.

P.S:

Do you mean by spatial complexity the number of lines in the algorithm ? or what ? thank you again.

@Markus : Your contribution is very helpful. Thank you

@Rafael : by the way, it would be absurd in my case of algorithms to set a theoretical complexity criterion, since my algorithms are mutually recursive and my source code right now is composed of at least 15000 lines of code !!

Check the run time and resource allocation ---- less run time more resources utilization is the better algorithm.

@Euldji, I dont think that empirical approach is better than theoretical one.

We must used one method or another considering the situation.

For example, in your case, is clear to me that you cannot use the theoretical approach. However, in my PhD thesis, i use both of them, but emphasizing in the theoretical measure.

Even complex algorithms can be compared with theoretical approach, notice that the algorithm not equal, necesary, to source code (15000 lines of code).

Spatial complexity is the amount of memory of an algorithm need to be executed. Usually when an algorithm (that solve the same problem) has a lower run time, this algorithm has a higer spatial complexity.

The important thing is: in all cases, there exists at least one way to compare two or more algorithms. Consecuently, when you propose an algorithm, you must show the advantages and disadvantages of the proposal.

Well first try to reverse engineer the programs you have if possible to get the source code and time stamps in appropriate places (start and end of algorithms) second if you want to compare the program as it than you can use some system benchmark tools to get the memory/processor consumption of each program. third if you are competent with the shell scripts you can get the execution time by calling the programs from the script while adding the timestamps. These will not calculate the aymptotic bounds of the algorithms but the runtime and memory consumption for you.

Many thanks

1."To compare a number of lines" - is not good. You have not the final-source. It will be machine-code, after compiling and optimising.

2. It's possible, that your program loads some dynamic libraries.

3. You can never get the exact time, if your program uses IO-chanels.

Theoretical approach is correct and you can define your own metrics to compare two algorithms.

1. Easiest to count the branches (if/else/switch - complexity).

2. You can try assembler-view of algorithms, and consider your problem in "MOVE" and "CALL" - commands.

3. "15000 lines of code" - envolve many algorithms: "Devide and Concuer", You can count all calls and check the stack.

4. If you can inject Aspects-Concerns in your sources, you win total control of your program, as black and white box.

Empirical approach, automatically:

1. Code-Metrics for time and memory

2. Aspects-oriented approach

3. Simulation and unit tests

Empirical approach, manual:

1. Profiler !!!

Don't forget, modern skills of algorithms are not ever a memory or speed. It's more important to have a clear architecture, to be able to make chieper modifications your sources, to have a pluginable sources, to have stable source.

Example: Q-Sort. - queek, small and simple - but not stable! merge-sort is huge and complex, but queek and stable.

*Algorithm != Code*

(Unless specific case is chosen for which this is true)

As a side notice, try to avoid confusion with two slightly different notions: an algorithm and a program. An algorithm is defined by the model of computation (e.g. turing machine) or a computer (algorithm does not care that much about its syntactical representation as long as it can run on some universal (turing-complete) computer - can be uniquely computed up to isomorhpism). Putting it simple an algorithm is a computer (method of computation). A program is defined/required to be at least syntactically correct according the grammar of a formal (programming) language. Semantics of behaviour of the program could be still wrong (or non-deterministic because you don't have a computer). A perfect example of showing computational equivalence is a Church–Turing thesis. Also check how deciding about language (program) equivalence can be matched with algorithmic equivalence, e.g. Chomsky hierarchy. Although such classification is sometimes considered rather vague (incomplete).

Note that the fact of this equivalence tells nothing about the speed or performance of your computation in real time. Any type of complexity measure is only an approximated estimate of algorithms performance. The only true way to measure the performance of your code is to run an actual computation. Obviously just considering full control graph (static code analyses) test is not enough (necessary but not sufficient).

Bottom line to measure your program speed you need a computer. If your computer is a theoretical one, such measuring would be merely a simulation (which strictly speaking all programs running on the computers literally are).

PS

If you are having problems profiling your code (which might be some sort of heuristics within full NP or bigger complexity class of problems, similar to BLAST), a good strategy is to bootstrap your datasets and show a comparison only for limited amount of runs. Yes, it is not very precise, but it might be sufficient for pragmatical reasons.

[EDIT]

Complexity estimates of algorithms should be given modulo computer (they are running on). In other words, if your abstraction of computational model is "fine", then your run-time complexity estimate is fine as well.

If you are just to optimize linear (not running in parallel) code for concrete CPU architecture try to achieve the pattern that your CPU is always 100% utilized and I/O is not a bottleneck. In general, rewriting your code in a faster language e.g. for C++ and using fast compilers can give you 10-100x speedup. Greater level of fine-tuning is to be picky about the architecture. Here I mean all the examples that will expose the differences between von Neumann and Harvard categories, including not just CPU arch.-diff as in RISC vs. CISC like in x86 vs. its modern descendants, but actually looking close at the processing unit itself.

Unfortunately with modern (CISC) multi-conveyor multi-core CPUs the picture is never as simple as linear . Namely having already two cores introduces a race condition into execution of your code.

Your further optimization options would be:

* rewriting critical sections in machine code (i.e. asm), tunning OS kernel or (even?) patch microCPU code might make your implementation might be even more optimal

* running computation in parallel (e.g. using HPC)

* going for "systems on a crystal" like FPGA

* looking for new models of computation like quantum computing

While designing logical circuits on FPGA is equivalent to actually building your own computer, using quantum computing is (almost, D-Wave?, other experimental constructs implementing quantum effects) not practically feasible. Nonetheless there is a huge layer of practical engineering possible for tuning and improving logical gates, electrical circuits, power consumption, etc.

Having that all said, the importance of finding asymptotic estimates for algorithmic computational time, big O (upper bound) vs. asymptotic equivalence (as defined by the lim or epsilon-delta notation for the functions' ratio) is not to be underestimated. As long as the computer algorithmic complexity estimate is given with approximation up to a model of computation (which could be even as detailed as a state-of-the-engineering machine) - such estimate is sufficient to provide a powerful insight into the computational nature of the problem. Note that in most cases turing-machine is only assumed as the definition of the algorithm, but little of it is taken into consideration while working with bigO asymptotic, etc.

@Salaheddin Juneidi : Thank you. But, isn't it better to have less run time and less resources utilization ? Or do you have a point that I'm still missing

@Rafael Rodríguez Puente : Thank you so much for your priceless answers.

I will try to find the theoretical complexity of my algorithms one by one. But, the true complexity in my case is the fact that I am using very complex mutual recursive strategy. Each time I make a specific test case to concur my theoretical approach, I find my abstraction wrong.

Even though, I will do as you say. Maybe I will find the solution for this kind of problem.

@Abdullah Yousafzai : The problem I have got actually is similar to compare the performance of microsoft office's word and my solution ! It's way to complicated to reverse engineer word. Unless you've got an idea :)

But I liked very much the fact that you mentioned the performance benchmarks tools, so I would be very grateful if you inform me of some of them

@Abderrahmane Euldji:

If U find your abstraction wrong, using a theoretical analysis, this maybe mean that U may analize another strategy or modify your approach.

Maybe if U publish your algorithm (or send me by email), i have a more clear idea of how to prove their correctness, and maybe i can sugest you a way to make the comparison.

@Sergey Gorainov : Your reply is so valuable. I will try to follow your "directives" as much as I can. Thank you so much

@Yauhen Yakimovich : I agree completely with you. But in order to test the performance when theoretical approach is extremely complicated in my case, then you have to pick a programming language and translate the algorithm.

I thank you so much for your reply. You gave a very good point

@everybody : I can't express my gratitude for your contribution. Thank you all so much.

I am really thrilled to read your next propositions and/or suggestions.

You can compare by their time, space and communication (if run into a parallel system) complexities.

The comparison is done regarding two axes i) the CPU computational time (time performance) ii) the solutions quality