HGPA

algorithm analysis

If you want to be a good programmer you just program every day for two years -- you'll be an excellent programmer. If you want to be a world-class programmer you can program every day for ten years, or you could program every day for two years and take an algorithms class.

Why do we need to analyze algorithms?

Asymptotic Analysis

We analyze an algorithm's complexity:

Usually we want an estimate of an algorithm's complexity in the asymptotic sense (large inputs).

There are three scenarios:

worst-case complexity:

average-case (expected) complexity:

best-case complexity:

Asymptotic Notation

Asymptotic notations:

big theta

big O

big omega

Orders of Growth

Orders of Growth

Running Time Name Fundamental Concept
O(1) constant instant operation independent of input n
O(log n) logarithmic "binary" (search, tree)
O(n) linear must read all n inputs
O(n log n) linearithmic O(log n) operations n times, divide-and-conquer
O(n^2) quadratic loop within a loop
O(c^n) exponential n values that each can be any c values, multi-call recursion, branches^depth
O(n!) factorial permutations of a list

Application

(TODO: WIP. HGPA)

We usually only care about Big O of worst-case. So what is the upper bound of the worst-case scenario of an algorithm?

WARNING: In industry the use of Big O is nearly synonymous with Big Θ (if applicable) in worst-case

References

Asymptotic Notation. Tom Cormen and Devin Balkcom. Algorithms. Kahn Academy.

Big O. Cracking the Code Interview. Sixth Edition. Gayle Laakmann McDowell.

Big-O Cheat Sheet. Eric Rowell. Tables with complexities of common data structures and algorithms.

Big O Notation. Brilliant.

Big O Notation. Interview Cake.

Big O notation. Wikipedia.

Getting Started. Introduction to Algorithms. Second Edition. CLRS. 2002.

Growth of Functions. Introduction to Algorithms. Second Edition. CLRS. 2002.

Lecture 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort. Charles Leiserson. Introduction to Algorithms. MIT OpenCourseWare. 2005 Fall.

Lecture 1: Algorithmic Thinking, Peak Finding. Srini Devadas. Introduction to Algorithms. MIT OpenCourseWare. 2011 Fall.

Recitation 1: Asymptotic Complexity, Peak Finding. Victor Costan. Introduction to Algorithms. MIT OpenCourseWare. 2011 Fall.

Filename: algorithm-analysis.md (Edit)
Modified: 2016-11-17 (46850cdbcdf3d677c151266aa95f6522269b495c)
Created: 2016-11-17 (46850cdbcdf3d677c151266aa95f6522269b495c)