Page 26 - DCAP407_DATA_STRUCTURE
P. 26

Rishi Chopra, Lovely Professional University               Unit 2: Complexity Analysis




                                       Unit 2: Complexity Analysis


               CONTENTS
               Objectives

               Introduction
               2.1 Mathematical Notation and Functions
                   2.1.1   Asymptotic Notations
                      2.1.2   Mathematical Functions
               2.2 Algorithmic Complexity and Time Space Tradeoff
                    2.2.1   Algorithmic Complexity

               2.3 Algorithmic Analysis
                      2.3.1   Types of Analysis
               2.4 Summary
               2.5 Keywords
               2.6 Self Assessment
               2.7 Review Questions
               2.8 Further Readings

               Objectives
               After studying this unit, you will be able to:

               •    Explain  mathematical notation and functions
               •    Analyze the algorithmic complexity and time space tradeoff
               •    Discuss algorithmic analysis
               Introduction

               Each computer program is a series of instructions that are arranged in a specific order to perform a
               specific task. A computer program is written to instruct a computer to perform a specific task in order to
               obtain  the  desired result.  Irrespective of the language used to develop a program, there are  some
               generic steps that can be  followed  to solve a problem.  These generic steps are called algorithms.
               According to H. Cormen, "Before there were computers, there were algorithms." An algorithm is a set of
               instructions that performs  a  particular task.  It  is considered as  a tool that helps to solve a specific
               computational problem.
               Mathematical notation  is a  system  of symbolic  representations of mathematical objects and ideas.
               Mathematical functions appear quite often in the analysis of algorithm along with their notation. Some
               of the mathematical functions are floor and ceiling functions, summation symbol, factorial, Fibonacci
               numbers, and so on.

               The complexity of an algorithm is a function that describes the efficiency of an algorithm in terms of the
               amount of data the algorithm must process.
               The two main complexity measures of efficiency of an algorithm are:
               1.   Time Complexity: It is a function that describes the time taken by an algorithm to solve a problem.

                              Big-O notation is used to express the time complexity of an algorithm.





                                        LOVELY PROFESSIONAL UNIVERSITY                           19
   21   22   23   24   25   26   27   28   29   30   31