How to calculate complexity algorithm code program?
6 views (last 30 days)
Show older comments
Bakka
on 28 Jan 2014
Commented: Walter Roberson
on 20 Apr 2020
Hi everyone, I've build program, now I want to calculate complexity algorithm ? could you please let me know how to do that? is there any reference for calculation process? Many thanks
3 Comments
Walter Roberson
on 29 Jan 2014
We cannot be of assistance in any analysis of RSA; the topic is forbidden for discussion here due to USA laws.
Accepted Answer
Walter Roberson
on 28 Jan 2014
You can google the topic.
It has been proven that there is no possible deterministic algorithm which can calculate the Algorithmic Complexity of all possible programs.
MATLAB does not provide any routines to calculate Algorithmic Complexity.
2 Comments
Hazim Nasir
on 19 Apr 2020
Kindly, Can you cite a reference that:
that there is no possible deterministic algorithm which can calculate the Algorithmic Complexity of all possible programs.
Walter Roberson
on 20 Apr 2020
This is a simple consequence of the (Turing's) Halting Theorem.
It is not possible to write a program, P1, that can take the code for any arbitrary program, P2, as input, with P1 telling you whether P2 halts on all possible inputs. The proof involves deliberate infinite loops and proof by contradiction on feeding a slightly modified version of P1 to itself. There are tight connections to Goedel's Incompleteness Theorem, that there are statements that are true but which cannot be formally proven to be true.
Anyhow, if you cannot write a program that can predict with certainty whether any given program will halt or not, then you cannot predict the algorithmic complexity of all arbitrary programs
More Answers (0)
See Also
Categories
Find more on Encryption / Cryptography in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!