ANALYSIS OF ALGORITHMS (Asymptotic Analysis )

Let’s learn about ANALYSIS OF ALGORITHMS (Asymptotic Analysis ).

INTRODUCTION

A common person’s belief is that a computer can do anything. This is far from the truth. In reality, the computer can perform only certain predefined instructions. The formal representation of this model as a sequence of instructions is called an algorithm, and coded algorithm, in a specific computer language is called a program. Analysis of algorithms has been an area of research in computer science; the evolution of very high-speed computers has not diluted the need for the design of time-efficient algorithms.

 

Complexity theory in computer science is a part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps (time) does it take to solve a problem) and space (how much memory does it take to solve a problem). It may be noted that complexity theory differs from computability theory, which deals with whether a problem can be solved or not through algorithms, regardless of the resources required.

 

Analysis of Algorithms is a field of computer science whose overall goal is to understand the complexity of algorithms. While an extremely large amount of research work is devoted to the worst-case evaluations, the focus in these pages is methods for average-case.  One can easily grasp that the focus has shifted from computer to computer programming and then to the creation of an algorithm. This is algorithm design, the heart of problem-solving.

• OBJECTIVES

After going through this unit, you should be able to:

• understand the concept of the algorithm;
• understand the mathematical foundation underlying the analysis of algorithm;
• to understand various asymptotic notations, such as Big O notation, theta notation and omega (big O, Θ, Ω ) for analysis of algorithms;
• understand various notations for defining the complexity of the algorithm;
• define the complexity of various well-known algorithms, and
• learn the method to calculate the time complexity of the algorithm.

 

Definition of Algorithm

An algorithm should have the following five characteristic features: –

1. Input
2. Output
3. Definiteness
4. Effectiveness
5. Termination.

Therefore, an algorithm can be defined as a sequence of definite and effective instructions, which terminates with the production of correct output from the given input.

Complexity classes

All decision problems fall into sets of comparable complexity, called complexity classes.

The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to the set of problems that can be effectively solved in the worst cases. We will consider algorithms belonging to this class for analysis of time complexity. Not all algorithms in these classes make practical sense as many of them have higher complexity. These are discussed later.

 

The complexity class NP is a set of decision problems that can be solved by a nondeterministic machine in polynomial time. This class contains many problems like the Boolean satisfiability problem, Hamiltonian path problem, and the Vertex cover problem.

What is Complexity?

Complexity refers to the rate at which the required storage or consumed time grows as a function of the problem size. The absolute growth depends on the machine used to execute the program, the compiler used to construct the program, and many other factors. We would like to have a way of describing the inherent complexity of a program (or piece of a program), independent of machine/compiler considerations. This means that we must not try to describe the absolute time or storage needed. We must instead concentrate on a “proportionality” approach, expressing the complexity in terms of its relationship to some known function. This type of analysis is known as asymptotic analysis.  It may be noted that we are dealing with the complexity of an algorithm not that of a problem. For example, a simple problem could have a high order of time complexity and vice-versa.

What kinds of problems are solved by algorithms?

Sorting is by no means the only computational problem for which algorithms have been developed. Practical applications of algorithms are ubiquitous and include the following examples:

• The Human Genome Project has made great progress toward the goals of identifying all the 100,000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. Each of these steps requires sophisticated algorithms. Although the solutions to the various problems involved are beyond the scope of this book, many methods to solve these biological problems use ideas from several of the chapters in this book, thereby enabling scientists to accomplish tasks while using resources efficiently. The savings are in time, both human and machine, and in money, as more information can be extracted from laboratory techniques.

 

• The Internet enables people all around the world to quickly access and retrieve large amounts of information. With the aid of clever algorithms, sites on the Internet a reliable to manage and manipulate this large volume of data. Examples of problems that make essential use of algorithms include finding good routes on which the data will travel and using a search engine to quickly find pages on which particular information resides.

 

 

•  Electronic commerce enables goods and services to be negotiated and exchanged electronically, and it depends on the privacy of personal information such as credit card numbers, passwords, and bank statements. The core technologies used in electronic commerce include public-key cryptography and digital signatures , which are based on numerical algorithms and number theory.
•    Manufacturing and other commercial enterprises often need to allocate scarce resources in the most beneficial way. An oil company may wish to know where to place its wells in order to maximize its expected profit. A political candidate may want to determine where to spend money buying campaign advertising in order to maximize the chances of winning an election. An airline may wish to assign crews to flights in the least expensive way possible, making sure that each flight is covered and that government regulations regarding crew schedules are met. An Internet service provider may wish to determine where to place additional resources in order to serve its customers more effectively. All of these are examples of problems that can be solved using linear programming.

          I hope guys like and comment on these posts  ANALYSIS OF ALGORITHMS ( Asymptotic Analysis ).

Read more…

Introduction to Data Structures | Classification | Data Structure Operation