26-07-2014, 11:40 AM
Analysis of Algorithms
Analysis.pdf (Size: 440.95 KB / Downloads: 10)
Overview
• Time complexity
- exact count of operations T(n) as a function of input size n
- complexity analysis using O(...) bounds
- constant time, linear, logarithmic, exponential,… complexities
• Complexity analysis of basic data structures’ operations
• Linear and Binary Search algorithms and their analysis
• Basic Sorting algorithms and their analysis
Time Complexity
• For most of the algorithms associated
with this course, time complexity
comparisons are more interesting than
space complexity comparisons
• Time complexity: A measure of the
amount of time required to execute an
algorithm
Time Complexity
• Analysis is based on the amount of
work done by the algorithm
• Time complexity expresses the
relationship between the size of the
input and the run time for the algorithm
• Usually expressed as a proportionality,
rather than an exact function
Intractable problems
• A problem is said to be intractable if
solving it by computer is impractical
• Example: Algorithms with time
complexity O(2n
) take too long to solve
even for moderate values of n; a
machine that executes 100 million
instructions per second can execute 260
instructions in about 365 years
13-29Constant Time Compl
Analysis: Radix Sort
• So, we perform 4*n enqueue and dequeue
operations each time through the outer loop
• Outer for loop is executed k times, so we have
4*k*n enqueue and dequeue operations
altogether
• But k is a constant, so the time complexity for
radix sort is O(n)
• COMMENT: If the maximum number of digits in
each number k is considered as a parameter
describing problem input, then complexity can be
written in general as O(n*k) or O(n*log(max_val)) 13-9