ANALYSIS OF ALGORITHM

-

ANALYSIS OF ALGORITHM :



 In theoretical analysis of algorithms, it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. The term "analysis of algorithms" was coined by Donald Knuth.

Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem. Most algorithms are designed to work with inputs of arbitrary length. Analysis of algorithms is the determination of the amount of time and space resources required to execute it.

Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity.

The Need for Analysis

In this chapter, we will discuss the need for analysis of algorithms and how to choose a better algorithm for a particular problem as one computational problem can be solved by different algorithms.

By considering an algorithm for a specific problem, we can begin to develop pattern recognition so that similar types of problems can be solved by the help of this algorithm.

Algorithms are often quite different from one another, though the objective of these algorithms are the same. For example, we know that a set of numbers can be sorted using different algorithms. Number of comparisons performed by one algorithm may vary with others for the same input. Hence, time complexity of those algorithms may differ. At the same time, we need to calculate the memory space required by each algorithm.

Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of analysis of algorithms is the required time or performance. Generally, we perform the following types of analysis −


  • Worst-case − The maximum number of steps taken on any instance of size a.

  • Best-case − The minimum number of steps taken on any instance of size a.

  • Average case − An average number of steps taken on any instance of size a.

  • Amortized − A sequence of operations applied to the input of size a averaged over time.



To solve a problem, we need to consider time as well as space complexity as the program may run on a system where memory is limited but adequate space is available or may be vice-versa. In this context, if we compare bubble sort and merge sort. Bubble sort does not require additional memory, but merge sort requires additional space. Though time complexity of bubble sort is higher compared to merge sort, we may need to apply bubble sort if the program needs to run in an environment, where memory is very limited.

Comments

Post a Comment

Popular posts from this blog

HANDWRITTEN NOTES (COMPUTER NETWORK ) USEFULL IN EXAMS (IMP TOPICS)

-
Image
COMPUTER NETWORK  HANDWRITTEN NOTES:                              👉  (IMP TOPICS )👈 WHAT IS COMPUTER NETWORK ? CHARACTICS OF COMPUTER NETWORK ? WHAT IS USE OF COMPUTER NETWORK? COMPUTER NETWORK ARCHITECTURE  PEER-PEER NETWORK CLIENT NETWORKS OSI MODEL(ALL LAYER) APPLICATION LAYER TCP/IP PROTOCOL DOWNLOAD HANDWRITTEN NOTES : 👇👇👇👇👇 SHARE THIS BLOG 😊
Read more

SESSION LAYER IN COMPUTER NETWORK

-
Image
  SESSION LAYER IN OSI MODEL : The session layer (layer 5) is responsible for establishing, managing, synchronizing and terminating sessions between end-user application processes. The main functions of the session layer are as follows − It works as a dialog controller. It allows the systems to communicate in either half-duplex or full-duplex mode of communication. It is responsible for token management. Through this, it prevents the two users to simultaneously attempt the same critical operation. It synchronizes communication. It adds synchronization points or checkpoints in data streams for long communications. This ensures that data streams up to the checkpoints are successfully received and acknowledged. In case of any failures, only the streams after the checkpoints have to be re-transmitted.
Read more

DATA STRUCTURE (IMP QUESTIONS )FOR (BE STUDENTS ,DIPLOMA STUNDENTS,UNIVERSITY) (CHEPTAR WISE )

-
Image
DATA STRUCTURE IMPORTANT QUESTIONS :  👇👇👇👇👇👇👇 QUESTIONS : 1 . WHAT IS DATA STRUCTURE AND TYPES OF DATA STRUCTURE ? 2.DIFFERENCE BETWEEN LINIEAR DATA AND NON LINEAR DATA STRUCTURE. 3 DIFFERNECE BETWEEN PRIMITIVE AND NON-PRIMITIVE DATA STRUCTURE . 4. WRITE ALGORITHM FOR PUSH AND POP STACK OPERATION 5.APPLICATION OF STACK AND QUEUE . 6. WRITE A C FUNCATION FOR INSERATION AND DELETION OPERATION IS SIMPLE QUEUE. 7.WRITE AN ALGORITHM TO DELETE AN ELEMENT FROM CIRCULAR QUEUE SHOWS THE STEPS OF INSERATION AND DELETION OPERATION IS SAMPLE CIRCULAR QUEUE. 8.DESCRIBE THE ADVANTAGE OF LINKED LIST OVER ARRY. 9.WRITE AN ALGORITHM TO INSERT A NODE ATLAST POSTION IN DOUBLY LINKED LIST. 10.EXPLAIN ARRAY IN DATA STRUCTURE .  11.WORKING OF PRIORITY QUEUE WITH SDING ORDER BY APPLYING QUUITABLE EXAMPLE . 12.WIRTE RECURSIVE ALGORITHMS TO COMPLETE FACTORIAL OF A GIVEN NUMVBERS WHICH DATA STRUCTURE CAN BE USED TO IMPLEMENT THIS ALGORITHMS. 13. SORT THE FOLLOWING NUMBER IN ASCENDING ORDER BY APPLYING QU
Read more