What are a posteriori and a priori analyses of algorithm operations?

Question

I am a new developer. Please help me understand what a posteriori and a priori analyses of algorithm operations are. I googled it, but I did not get any proper answers.

Solution 1

Apriori analysis of algorithms : it means we do analysis (space and time) of an algorithm prior to running it on specific system - that is, we determine time and space complexity of algorithm by just seeing the algorithm rather than running it on particular system (with different processor and compiler).

Apostiari analysis of algorithms : it means we do analysis of algorithm only after running it on system. It directly depends on system and changes from system to system.

In industry we cannot do Apostiari analysis as software is generally made for an anonymous user which runs it on system different (in processor like Pentium 3 or Pentium 4) from those present in the industry.

In Apriory it is the reason we use asymptotic notations to determine time and space complexity as they changes from computer to computer but asymptotically they are same.

Solution 2

In short

In an priory analysis, we obtain a function which bounds the algorithm computing time.

In a posteriori analysis, we collect actual statistics about the algorithms consumption of time and space, while it is executing.

Here is the book.

Somewhat longer:

Wikipedia definition

Ans another article citation

By far the most important reason to analyze an algorithm is to make sure it will correctly solve your problem. If our algorithm doesn't work, nothing else matters. So we must analyze it to prove that it will always work as expected.

We must also look at the efficiency of our algorithm. If it solves our problem, but does so in O(nn) time (or space!), then we should probably look at a redesign.

Solution 3

A Priori Analysis − This is all about the theoretical analysis of an algorithm. theWhere efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.

A Posterior Analysis − This is more of an empirical analysis of an algorithm. The selected algorithm is implemented using programming language and then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

Solution 4

In posterior analysis we run the algo on a system to check its original statics so that we can calculate its time and space complexity. but since it changes from system to system so it is not that effective. we calculate its time complexity in terms of a specific system requirements.

In prior analysis we only see the algo and give its analysis in terms of asymptotic notations. It doesn't change system to system in terms of asymptotic notation.

View more solutions

Comments

[Basile Starynkevitch]

I don't understand your question. Are you talking of "post-mortem crash analysis" or do you want to do "static analysis of source code" ?

[Zeta]

Do you mean adaptive approximation of PDEs via a posteriori and a priori error estimates? This is my first thought, but I bet you didn't mean that. You should add more details.

[Jonathan Leffler]

Google search for 'a priori algorithm analysis operation' suggests a Wikipedia page on Apriori Algorithm which has the helpful comment at the top that 'this article may be confusing or unclear to readers'. Replace 'priori' with 'posteriori' and you don't get a Wikipedia page showing until you add 'site:wikipedia.org', and then you get A priori and a posteriori. Maybe they'll help — maybe they won't.