Algorithm Analysis

4 Key excerpts on "Algorithm Analysis"

• 

  eBook - ePub

  Theory of Computation Simplified

  Simulate Real-world Computing Machines and Problems with Strong Principles of Computation (English Edition)

  • Dr. Varsha H. Patil, Dr. Vaishali S. Pawar, Dr. Swati A. Bhavsar, Dr. Aboli H. Patil(Authors)
  • 2022(Publication Date)
  • BPB Publications

    (Publisher)

  Algorithmics is a field of computer science, defined as the study of algorithms. The overall goal of algorithmics is an understanding of the complexity of algorithms. The study includes the design and analysis of algorithms.

  Although computer scientists have studied algorithms and algorithm efficiency extensively, the field has not been given an official name. Brassard and Bratley coined the term algorithmics, which they defined as the systematic study of the fundamental techniques used to design and analyze efficient algorithms.

  When we want to solve a problem, there may be a choice of algorithms available. In such a case, it is important to decide which one to use. Depending on our priorities and the limits of the equipment available to use, we may want to choose an algorithm that takes the least time or uses the least storage or is the easiest to program and so on. The answer can depend on many factors, such as the number involved, the way the problem is presented, or the speed and storage capacity of the available computing equipment.

  It may be possible that none of the available algorithms is entirely suitable, and therefore, we have to design a new algorithm of our own. Algorithmics is the science that lets us evaluate the effect of these various external factors on the available algorithms, so that we can choose the one that best suits our particular circumstances; it is also the science that tells us how to design a new algorithm.

  Algorithmics include the following:

  • How to devise algorithms

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Recursive Programming

  • Manuel Rubio-Sanchez(Author)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  3

  Runtime Analysis of Recursive Algorithms

  The faster you go, the shorter you are. —Albert Einstein

  A LGORITHM analysis is the field that studies how to theoretically estimate the resources that algorithms need in order to solve computational problems. This chapter focuses on analyzing the runtime, also denoted as “computational time complexity,” of recursive algorithms that solve problems whose size depends on a single factor (which occurs in the majority of the problems covered in the book). This will provide a context that will enable us to characterize and compare different algorithms regarding their efficiency. In particular, the chapter describes two methods for solving recurrence relations, which are recursive mathematical functions that describe the computational cost of recursive algorithms. These tools are used in order to transform a recurrence relation into an equivalent nonrecursive function that is easier to understand and compare. In addition, the chapter provides an overview of essential mathematical fundamentals and notation used in the analysis of algorithms. Lastly, the analysis of memory (storage) or space complexity of recursive algorithms will be covered in Chapter 10 .

  3.1 MATHEMATICAL PRELIMINARIES

   

  This section presents a brief introduction to basic mathematical definitions and properties that appear in the analysis of the computational complexity of algorithms, and in several problems covered throughout the book.

  3.1.1 Powers and logarithms

  The following list reviews essential properties of powers and logarithms:

  where a , b , x , and y are arbitrary real numbers, with the exceptions that: (1) the base of a logarithm must be positive and different than 1, (2) a logarithm is only defined for positive numbers, and (3) the denominator in a fraction cannot be 0. For example,

  log b

  x =

  log a

  x /

  log a

  b

  is only valid for

  a > 0

  with

  a ≠ 1

  ,

  b > 0

  with

  b ≠ 1

  , and

  x > 0

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Consumer Optimization Problem Solving

  • Alfred L Norman(Author)
  • 2014(Publication Date)
  • WSPC

    (Publisher)

  Analyzing human algorithms requires a very different approach than analyzing computer algorithms. Computer algorithms are specified so that they can be mathematically analyzed. Human algorithms must be inferred from human behavior. The fact that computational complexity definitions are based on a fixed cost of elementary operations does not create a problem in analyzing human procedures. With learning, the cost of performing an elementary operation is likely to decline. This does not affect the computational complexity definitions as long as there is a lower bound representing the learning limit. The definitions strip constants in determining to which equivalence class an algorithm belongs.

  To determine the difficultly in solving a problem with a computer algorithm the researcher constructs an algorithm and shows that a more efficient algorithm does not exist, thus establishing the computational complexity of the problem. The approach is to use mathematical analysis of the specified algorithm, for example [Norman and Jung (1977)]. A traditional computational complexity approach can be used to study economic theory, such as providing an explanation for money, [Norman (1987)] and a Bayesian explanation of F. Knight’s uncertainty versus risk, [Norman and Shimer (1994)]. For a discussion of the relationship between computability, complexity and economics see [Velupillai (2010)] and [Velupillai (2005)].

  In studying procedures used by humans the procedure must be inferred from the subjects’ behavior. Analysis of human procedures can be done by watching the hand motions of subjects handling the test objects or which buttons the subjects click on a computer screen. Also, asking the subjects what they are doing can be illuminating. Algorithms that are members of different equivalence classes can be identified using statistical techniques such as regression analysis. We use these approaches in determining what procedures humans use in ordering alternatives in Chapter 3

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  40 Algorithms Every Programmer Should Know

  Hone your problem-solving skills by learning different algorithms and their implementation in Python

  • Imran Ahmad(Author)
  • 2020(Publication Date)
  • Packt Publishing

    (Publisher)

  The performance of a typical algorithm will depend on the type of the data given to it as an input. For example, if the data is already sorted according to the context of the problem we are trying to solve, the algorithm may perform blazingly fast. If the sorted input is used to benchmark this particular algorithm, then it will give an unrealistically good performance number, which will not be a true reflection of its real performance in most scenarios. To handle this dependency of algorithms on the input data, we have different types of cases to consider when conducting a performance analysis.

  Passage contains an image

  The best case

  In the best case, the data given as input is organized in a way that the algorithm will give its best performance. Best-case analysis gives the upper bound of the performance.

  Passage contains an image

  The worst case

  The second way to estimate the performance of an algorithm is to try to find the maximum possible time it will take to get the job done under a given set of conditions. This worst-case analysis of an algorithm is quite useful as we are guaranteeing that regardless of the conditions, the performance of the algorithm will always be better than the numbers that come out of our analysis. Worst-case analysis is especially useful for estimating the performance when dealing with complex problems with larger datasets. Worst-case analysis gives the lower bound of the performance of the algorithm.

  Passage contains an image

  The average case

  This starts by dividing the various possible inputs into various groups. Then, it conducts the performance analysis from one of the representative inputs from each group. Finally, it calculates the average of the performance of each of the groups.

  Sign up to read

  Learn more about book