Analysis of Algorithm:Time Complexity

Efficiency of an algorithm can be measured in terms of:
• Execution time (time complexity)
• The amount of memory required (space complexity)

Due to limitation of time over technology , the time complexity is much more interesting than space complexity.

• Time complexity: A measure of the amount of time required to execute an algorithm.

Factors that should not affect time complexity analysis:
• The programming language chosen to implement the algorithm
• The quality of the compiler
• The speed of the computer on which the algorithm is to be executed

In fact, Time complexity analysis for an algorithm is independent of programming language,machine used.


Objectives of time complexity analysis:
• To determine the feasibility of an algorithm by estimating an upper bound on the amount of work performed
• To compare different algorithms before deciding on which one to implement



• 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.
• To simplify analysis, we sometimes ignore work that takes a constant amount of time, independent of the problem input size
• When comparing two algorithms that perform the same task, we often just
concentrate on the differences between algorithms


• Simplified analysis can be based on:

--Number of arithmetic operations performed
--Number of comparisons made
--Number of times through a critical loop
--Number of array elements accessed
--etc


Example: Polynomial Evaluation
Suppose that exponentiation is carried out using multiplications. Two ways to evaluate the polynomial







are:
Brute force method:
p(x) = 4*x*x*x*x + 7*x*x*x – 2*x*x + 3*x + 6
Horner’s method:
p(x) = (((4*x + 7) * x – 2) * x + 3) * x + 6


•Method of analysis:
• Basic operations are multiplication, addition, and subtraction
• We’ll only consider the number of multiplications, since the number of additions and subtractions are the same in each solution
• We’ll examine the general form of a polynomial of degree n, and express our result in terms of n
• We’ll look at the worst case (max number of multiplications) to get an upper bound on the work
General form of polynomial is








Analysis for Brute Force Method:
p(x) = an * x * x * ... * x * x +                             n multiplications
a n-1 * x * x * ... * x * x +                                 n-1 multiplications
a n-2 * x * x * ... * x * x +                                 n-2 multiplications
...+ ...
a2 * x * x +                                                         2 multiplications
a1 * x +                                                             1  multiplication
a0


Number of multiplications needed in the worst case is
T(n) = n + n-1 + n-2 + ... + 3 + 2 + 1
= n(n + 1)/2                   (result from high school math **)
= n2/2 + n/2
This is an exact formula for the maximum number of multiplications. In general though, analyses yield upper bounds rather than exact formulae. We say that
the number of multiplications is on the order of n2, or O(n2). (Think of this as being proportional to n2.)         (** We’ll give a proof for this result a bit later)


Analysis for Horner’s Method:
p(x) = ( ... ((( an * x +                                           1 multiplication   ......
            an-1) * x +                                                1 multiplication         .
           an-2) * x +                                                 1 multiplication         .
            ...+                                                                                              .
                                                                                                                . n times
         a2) * x +                                                      1 multiplication         .
         a1) * x +                                                     1 multiplication          .
         a0                                                                                             ......
T(n) = n, so the number of multiplications is O(n)


Time Complexity(1) continues..........