anlysis of algorithm

A framework for perdicting performance and comparing algorithms.

• Observe some feature of the natural world.

• Hypothesize a model that is consistent with the observations.

• Predict events using the hypothesis.

• Verify the predictions by making further observations.

• Validate by repeating until the hypothesis and observations agree.

Best case. Lower bound on cost.

• Determined by “easiest” input.
• Provides a goal for all inputs.

Worst case. Upper bound on cost.

• Determined by “most difficult” input.
• Provides a guarantee for all inputs.

Average case. Expected cost for random input.

• Need a model for “random” input.
• Provides a way to predict performance.

Goals.

• Establish “difficulty” of a problem and develop “optimal” algorithms.
• Ex.1-Sum=”Is there a 0 in the array”

Upper bound.

• Ex. Brute-force algorithm for 1-Sum: Look at every array entry.
• Running time of the optimal algorithm for 1-Sum is O(N)

Lower bound.

• Ex. Have to examine all N entries (any unexamined one might be 0).
• Running time of the optimal algorithm for 1-SUM is Ω(N).

Optimal algorithm.

• Lower bound equals upper bound (to within a constant factor).
• Ex. Brute-force algorithm for 1-SUM is optimal: its running time is Θ(N ).

Goals.

• Establish “difficulty” of a problem and develop “optimal” algorithms.
• Ex.3-Sum

Upper bound.

• Ex. Improved algorithm for 3-Sum.
• Running time of the optimal algorithm for 3-Sum is O(N^2logN )

Lower bound.

• Ex. Have to examine all N entries for 3-Sum.
• Running time of the optimal algorithm for 3-SUM is Ω(N).

• Bit. 0 or 1.
• Byte. 8 bits.
• Megabyte(MB). 1 million or 2^20 bytes.
• Gigabyte(GB). 1 billion or 2^30 bytes.

• Object overhead 16 bytes.
• Reference 8 bytes.
• Padding Each object uses a multiple of 8 bytes.

Total memroy usage for a data type value:

• Primitive type: 4 bytes for int, 8 bytes for double, …
• Object reference: 8 bytes.
• Array: 24 bytes + memory for each array entry.
• Object: 16 bytes + memory for each instance variable + 8 bytes if inner class (for pointer to enclosing class).
• Padding: round up to multiple of 8 bytes.