Complexity analysis of algorithms

[nbro]

This project also aims at implementing algorithms which asymptotically are faster than their eventual alternatives. Nevertheless, asymptotically slower alternatives are not excluded: on the contrary, they may serve as a form of comparison (for the purposes of better understanding the complexity analysis, given that this project is mainly educational) with the theoretically asymptotically faster ones. Moreover, in practice, algorithms with lower asymptotic complexity may have a better runtime performance, at least for certain inputs and/or for certain architectures.

The goals of this issue (which is going to be permanent) are:

1. Ensure asymptotically fastest algorithms for a particular problem are implemented before the slower ones.

2. Implement interesting alternatives to the asymptotically fastest algorithms. Interesting alternatives are e.g. the ones that in practice (at least for certain inputs) perform better than the asymptotically fastest algorithms.

3. List and point to resources that may help in analyzing the implemented algorithms.

4. Take also into consideration the space complexity analysis of algorithms, which, so far, has not been performed much.

5. Describe (usual) techniques to compare asymptotic complexities of two algorithms. This may be useful e.g. if one wants to order (increasingly or decreasingly) algorithms according to their asymptotic growth rate [OPTIONAL].

6. List facts about the asymptotic behavior of functions. For example, polynomials grow slower than exponentials [OPTIONAL].

---

Asymptotic complexity of common algorithms

• http://bigocheatsheet.com/

General explanations about asymptotic notation

• https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

Order functions according to their asymptotic growth rate

• https://cseweb.ucsd.edu/classes/su00/cse101/l2.pdf

• http://www.orcca.on.ca/~yxie/courses/cs2210b-2011/htmls/asns/asn1/sol-asn1-CS2210b-2011.pdf

• https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/functions-in-asymptotic-notation

• http://www.orcca.on.ca/~yxie/courses/cs2210b-2011/htmls/asns/sol-mid-cs2210b-2011.pdf

• https://carlstrom.com/stanford/cs161/ps1sol.pdf

• https://stackoverflow.com/questions/9542536/why-is-the-following-sequence-of-functions-ordered-by-asymptotic-growth-rates

• https://courses.cs.washington.edu/courses/cse373/05sp/homework/hw2/373-HW2soln.pdf

• https://web.cs.wpi.edu/~cs2223/b05/Exams/Exam1/

• http://www.math.purdue.edu/~sbasu/teaching/fall06/cs3510/sol1.pdf

• http://www.techtud.com/sites/default/files/public/share/AsymptoticNotation.pdf

• http://cse.unl.edu/~sscott/teach/Classes/cse156S06/Notes/AsymptoticNotation.pdf

• https://cs-people.bu.edu/xmeng/cs330/notes/lab2.pdf

• http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Growth-of-Functions.pdf

• https://www.cs.duke.edu/brd/Teaching/230/handouts/order-of-growth2.pdf

• https://www.math.psu.edu/sites/default/files/public/migration/141rates1.pdf

• https://umutzafer.files.wordpress.com/2012/01/solu2.pdf

• https://www.cs.umd.edu/~mount/251/Handouts/cmsc251-nosol.pdf

• https://math.stackexchange.com/questions/1382947/how-to-recognise-intuitively-which-functions-grow-faster-asymptotically

• https://math.stackexchange.com/questions/2461451/which-one-grows-asymptotically-faster-gn-10120-n-sqrtn-or-fn-3

• Chapter 2 of "Algorithm Design" (by Kleinberg and Tardos).