Complexity Analysis

Algorithm

A finite sequence of precise instructions for performing a computation for solving a problem.

Computational complexity

Measure of the processing time required by the algorithm to solve problems of a particular problem size.

Time, Space

Time complexity of Algorithm

The size of the problem: an integer n
1. #inputs(ex: sorting problem, 2+3//20+3+10+5....)
2. #digits of input(ex: primality problem 2+3=5//12345+78910..)
3. sometimes more than one integer

Objective: characterize the running time of an algorithm for increasing problem sizes

Good unit of time

number of code fragments that take constant time

Worst-Case Analysis

• Worst case running time
• largest possible runnig time of algorithm

Efficiency of Algorithms

Objective
: Analyze algorithms independently of specific implementations, hardware of data

Observation
: An algorithm's execution time is related to the number of operations it executes

Solution
: The number of STEPS- significant time, operations

Notation

Constant

Linear

Logarithm

ex: Binary Search