Abstract: In this paper, the age-old definition of complexity is explained with example algorithms. With the emergence of more complex algorithms this definition of complexity needs a revisit. Three types of algorithms with complexity issues are discussed here. (1) In case of machine learning algorithms, complexity depends on samples that are learnt. To combat this situation, an additional term sample complexity is introduced. Often some of / all the available samples are erroneous. Possibility of learning errors makes the situation very complex. Instead of complexity estimation a yes / no decision for algorithm execution with restricted resources might prove simpler and more realistic. (2) For evolutionary computation, a randomized algorithm, the process path is different in each execution even for same input and output. Estimation of complexity is a challenge for this case. As the worst path takes infinite time yes / no decision always gives the answer as “no”. (3) Complexity of cryptographic algorithms largely depends on the size of some input integers deciding the key for cryptography. One algorithm with a smaller key and hence less complexity may provide more security over the other. Complexity should be compared for the same level of security. So far there is no model for estimation of security. Security is an experimental parameter. Without any security model it is pointless to estimate complexity for cryptographic algorithms.
Keywords: algorithms, cryptography, evolutionary, machine-learning, complexity
Volume 7, Issue 1, 2020