Share
VIDEOS 1 TO 50
Algorithms Lecture 1 -- Introduction to asymptotic notations
Algorithms Lecture 1 -- Introduction to asymptotic notations
Published: 2014/06/05
Channel: Gate Lectures by Ravindrababu Ravula
Big O Algorithm Analysis Part 1 - Big Oh
Big O Algorithm Analysis Part 1 - Big Oh
Published: 2015/10/22
Channel: CSBreakdown
Time complexity analysis - How to calculate running time?
Time complexity analysis - How to calculate running time?
Published: 2012/12/03
Channel: mycodeschool
Stanford Lecture - Don Knuth: The Analysis of Algorithms
Stanford Lecture - Don Knuth: The Analysis of Algorithms
Published: 2017/01/30
Channel: stanfordonline
1. Analysis of Algorithms Introduction
1. Analysis of Algorithms Introduction
Published: 2014/08/13
Channel: Algorithms and Data Structures
Algorithms lecture 2 -- Time complexity Analysis of iterative programs
Algorithms lecture 2 -- Time complexity Analysis of iterative programs
Published: 2014/06/06
Channel: Gate Lectures by Ravindrababu Ravula
Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
Published: 2009/01/07
Channel: MIT OpenCourseWare
Big O Notations
Big O Notations
Published: 2013/03/19
Channel: Derek Banas
Chapter 2 Analysis of Algorithm in DS Hindi
Chapter 2 Analysis of Algorithm in DS Hindi
Published: 2015/03/13
Channel: Data Structure by Saurabh Shukla Sir
Algorithms Lesson 6: Big O, Big Omega, and Big Theta Notation
Algorithms Lesson 6: Big O, Big Omega, and Big Theta Notation
Published: 2010/02/19
Channel: xoaxdotnet
Programming Interview: Analysis of Algorithm (Best case, Average case, Worst case)
Programming Interview: Analysis of Algorithm (Best case, Average case, Worst case)
Published: 2013/04/05
Channel: saurabhschool
The Big Oh! (Part 1) | Algorithm Analysis
The Big Oh! (Part 1) | Algorithm Analysis
Published: 2016/08/04
Channel: Estefannie Explains It All
Analysis of Algorithms
Analysis of Algorithms
Published: 2015/10/19
Channel: Princeton Online
Donald Knuth - Why I chose analysis of algorithms as a subject (97/97)
Donald Knuth - Why I chose analysis of algorithms as a subject (97/97)
Published: 2016/01/07
Channel: Web of Stories - Life Stories of Remarkable People
Time complexity analysis: asymptotic notations - big oh, theta ,omega
Time complexity analysis: asymptotic notations - big oh, theta ,omega
Published: 2012/12/03
Channel: mycodeschool
Design and Analysis of Algorithms I
Design and Analysis of Algorithms I
Published: 2011/11/19
Channel: mlClassStaff
What is Complexity Analysis of Algorithms?
What is Complexity Analysis of Algorithms?
Published: 2015/02/15
Channel: Quinston Pimenta
Summations and Algorithm Analysis
Summations and Algorithm Analysis
Published: 2015/04/26
Channel: randerson112358
Lecture - 2 Framework for Algorithms Analysis
Lecture - 2 Framework for Algorithms Analysis
Published: 2008/08/26
Channel: nptelhrd
5. Amortization: Amortized Analysis
5. Amortization: Amortized Analysis
Published: 2016/03/04
Channel: MIT OpenCourseWare
Time complexity analysis - some general rules
Time complexity analysis - some general rules
Published: 2012/12/08
Channel: mycodeschool
Types of Algorithm Analysis: Best Case, Worst Case, and Average case
Types of Algorithm Analysis: Best Case, Worst Case, and Average case
Published: 2016/04/21
Channel: Narasimha Karumanchi
Algorithms } 004 } Analysis of Algorithms } Time and Space complexity }
Algorithms } 004 } Analysis of Algorithms } Time and Space complexity }
Published: 2015/08/17
Channel: Leprofesseur }
HOW TO FIND TIME AND SPACE COMPLEXITY OF ALGORITHMS
HOW TO FIND TIME AND SPACE COMPLEXITY OF ALGORITHMS
Published: 2014/04/04
Channel: vamshi krishna Nellutla
Lecture 3: Fundamentals of the Analysis of  Algorithm Efficiency -1
Lecture 3: Fundamentals of the Analysis of Algorithm Efficiency -1
Published: 2016/09/05
Channel: iugaza1
Analysis of algorithms
Analysis of algorithms
Published: 2011/01/14
Channel: Oresoft LWC
Analysis and Design of Algorithms
Analysis and Design of Algorithms
Published: 2013/02/07
Channel: Garden City University
Algorithms Lecture 7 -- Insertion sort algorithm and analysis
Algorithms Lecture 7 -- Insertion sort algorithm and analysis
Published: 2014/07/02
Channel: Gate Lectures by Ravindrababu Ravula
Algorithms lecture 13-- Build max heap algorithm and analysis
Algorithms lecture 13-- Build max heap algorithm and analysis
Published: 2014/07/04
Channel: Gate Lectures by Ravindrababu Ravula
Algorithms lecture 3 -- Time analysis of recursive program
Algorithms lecture 3 -- Time analysis of recursive program
Published: 2014/06/12
Channel: Gate Lectures by Ravindrababu Ravula
Analysis of Algorithms Orders of growth worst best avg case complexity
Analysis of Algorithms Orders of growth worst best avg case complexity
Published: 2014/03/13
Channel: jadavparesh808
Algorithms lecture 10 -- Analysis of quick sort and problems on it
Algorithms lecture 10 -- Analysis of quick sort and problems on it
Published: 2014/07/03
Channel: Gate Lectures by Ravindrababu Ravula
Algorithms } 007 } Analysis of randomized algorithms }
Algorithms } 007 } Analysis of randomized algorithms }
Published: 2015/09/11
Channel: Leprofesseur }
Analysis of Algorithms Measuring efficiency Part 1
Analysis of Algorithms Measuring efficiency Part 1
Published: 2014/03/13
Channel: jadavparesh808
Amortized Analysis
Amortized Analysis
Published: 2016/11/16
Channel: 0612 TV w/ NERDfirst
Time and space complexity analysis of recursive programs - using factorial
Time and space complexity analysis of recursive programs - using factorial
Published: 2012/10/10
Channel: mycodeschool
Lecture - 3 Algorithms Analysis Framework - II
Lecture - 3 Algorithms Analysis Framework - II
Published: 2008/08/26
Channel: nptelhrd
1   8   Guiding Principles for Analysis of Algorithms 15 min
1 8 Guiding Principles for Analysis of Algorithms 15 min
Published: 2017/01/27
Channel: Stanford Algorithms
Analysis of Non recursive Algorithms
Analysis of Non recursive Algorithms
Published: 2014/03/13
Channel: jadavparesh808
Donald Knuth - A new field: analysis of algorithms (37/97)
Donald Knuth - A new field: analysis of algorithms (37/97)
Published: 2016/02/11
Channel: Web of Stories - Life Stories of Remarkable People
Algorithm Analysis in Data Structure by Computer Education part 1
Algorithm Analysis in Data Structure by Computer Education part 1
Published: 2016/03/12
Channel: Computer Education For all
Time Complexity analysis of recursion - Fibonacci Sequence
Time Complexity analysis of recursion - Fibonacci Sequence
Published: 2012/10/10
Channel: mycodeschool
Analysis of Algorithm to find Maximum and Minimum element from an Array - Part 2
Analysis of Algorithm to find Maximum and Minimum element from an Array - Part 2
Published: 2017/01/19
Channel: StudyKorner
Brief History: From Analysis of Algorithms to Analytic Combinatorics - Robert Sedgewick
Brief History: From Analysis of Algorithms to Analytic Combinatorics - Robert Sedgewick
Published: 2015/11/07
Channel: Alexander Grothendieck
TIME COMPLEXITY(in Hindi- Human Language) - Lec 1
TIME COMPLEXITY(in Hindi- Human Language) - Lec 1
Published: 2014/03/14
Channel: Algorithm World
Analysis of quicksort
Analysis of quicksort
Published: 2013/12/16
Channel: mycodeschool
TIME COMPLEXITY OF ALGORITHMS IN HINDI
TIME COMPLEXITY OF ALGORITHMS IN HINDI
Published: 2016/02/14
Channel: LearnEveryone
Binary Search Algorithm : Divide and Conquer Technique : Think Aloud Academy
Binary Search Algorithm : Divide and Conquer Technique : Think Aloud Academy
Published: 2012/05/05
Channel: ThinkAloudAcademy
Algorithm lecture 8 -- Merge sort algorithm, analysis and problems
Algorithm lecture 8 -- Merge sort algorithm, analysis and problems
Published: 2014/07/02
Channel: Gate Lectures by Ravindrababu Ravula
Design and Analysis of Algorithm(DAA) | Master
Design and Analysis of Algorithm(DAA) | Master's Theorem
Published: 2017/01/16
Channel: Last Minute Tutorials
NEXT
GO TO RESULTS [51 .. 100]

WIKIPEDIA ARTICLE

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For looking up a given entry in a given ordered list, both the binary and the linear search algorithm (which ignores ordering) can be used. The analysis of the former and the latter algorithm shows that it takes at most log2(n) and n check steps, respectively, for a list of length n. In the depicted example list of length 33, searching for "Morin, Arthur" takes 5 and 28 steps with binary (shown in cyan) and linear (magenta) search, respectively.
Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N versus input size n for each function

In computer science, the analysis of algorithms is the determination of the amount of time, storage and/or other resources necessary to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small. Since different inputs of the same length may cause the algorithm to have different behavior, the function describing its performance is usually an upper bound on the actual performance, determined from the worst case inputs to the algorithm.

The term "analysis of algorithms" was coined by Donald Knuth.[1] Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms.

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. Big O notation, Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the length of the sorted list being searched, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant.

Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation. A model of computation may be defined in terms of an abstract computer, e.g., Turing machine, and/or by postulating that certain operations are executed in unit time. For example, if the sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log2 n + 1 time units are needed to return an answer.

Cost models[edit]

Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual execution time, the time required to perform a step must be guaranteed to be bounded above by a constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.

Two cost models are generally used:[2][3][4][5][6]

  • the uniform cost model, also called uniform-cost measurement (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved
  • the logarithmic cost model, also called logarithmic-cost measurement (and similar variations), assigns a cost to every machine operation proportional to the number of bits involved

The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography.

A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.[7]

Run-time analysis[edit]

Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time) of an algorithm as its input size (usually denoted as n) increases. Run-time efficiency is a topic of great interest in computer science: A program can take seconds, hours, or even years to finish executing, depending on which algorithm it implements. While software profiling techniques can be used to measure an algorithm's run-time in practice, they cannot provide timing data for all infinitely many possible inputs; the latter can only be achieved by the theoretical methods of run-time analysis.

Shortcomings of empirical metrics[edit]

Since algorithms are platform-independent (i.e. a given algorithm can be implemented in an arbitrary programming language on an arbitrary computer running an arbitrary operating system), there are additional significant drawbacks to using an empirical approach to gauge the comparative performance of a given set of algorithms.

Take as an example a program that looks up a specific entry in a sorted list of size n. Suppose this program were implemented on Computer A, a state-of-the-art machine, using a linear search algorithm, and on Computer B, a much slower machine, using a binary search algorithm. Benchmark testing on the two computers running their respective programs might look something like the following:

n (list size) Computer A run-time
(in nanoseconds)
Computer B run-time
(in nanoseconds)
16 8 100,000
63 32 150,000
250 125 200,000
1,000 500 250,000

Based on these metrics, it would be easy to jump to the conclusion that Computer A is running an algorithm that is far superior in efficiency to that of Computer B. However, if the size of the input-list is increased to a sufficient number, that conclusion is dramatically demonstrated to be in error:

n (list size) Computer A run-time
(in nanoseconds)
Computer B run-time
(in nanoseconds)
16 8 100,000
63 32 150,000
250 125 200,000
1,000 500 250,000
... ... ...
1,000,000 500,000 500,000
4,000,000 2,000,000 550,000
16,000,000 8,000,000 600,000
... ... ...
63,072 × 1012 31,536 × 1012 ns,
or 1 year
1,375,000 ns,
or 1.375 milliseconds

Computer A, running the linear search program, exhibits a linear growth rate. The program's run-time is directly proportional to its input size. Doubling the input size doubles the run time, quadrupling the input size quadruples the run-time, and so forth. On the other hand, Computer B, running the binary search program, exhibits a logarithmic growth rate. Quadrupling the input size only increases the run time by a constant amount (in this example, 50,000 ns). Even though Computer A is ostensibly a faster machine, Computer B will inevitably surpass Computer A in run-time because it's running an algorithm with a much slower growth rate.

Orders of growth[edit]

Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n0 and a constant c, the running time of that algorithm will never be larger than . This concept is frequently expressed using Big O notation. For example, since the run-time of insertion sort grows quadratically as its input size increases, insertion sort can be said to be of order O(n2).

Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case — for example, the worst-case scenario for quicksort is O(n2), but the average-case run-time is O(n log n).

Empirical orders of growth[edit]

Assuming the execution time follows power rule, t ≈ k na, the coefficient a can be found [8] by taking empirical measurements of run time at some problem-size points , and calculating so that . In other words, this measures the slope of the empirical line on the log–log plot of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule (and so the line on log–log plot is indeed a straight line), the empirical value of a will stay constant at different ranges, and if not, it will change (and the line is a curved line) - but still could serve for comparison of any two given algorithms as to their empirical local orders of growth behaviour. Applied to the above table:

n (list size) Computer A run-time
(in nanoseconds)
Local order of growth
(n^_)
Computer B run-time
(in nanoseconds)
Local order of growth
(n^_)
15 7 100,000
65 32 1.04 150,000 0.28
250 125 1.01 200,000 0.21
1,000 500 1.00 250,000 0.16
... ... ...
1,000,000 500,000 1.00 500,000 0.10
4,000,000 2,000,000 1.00 550,000 0.07
16,000,000 8,000,000 1.00 600,000 0.06
... ... ...

It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than the first one.

Evaluating run-time complexity[edit]

The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions. Consider the following pseudocode:

1    get a positive integer from input
2    if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be deterministic.[9] Say that the actions carried out in step 1 are considered to consume time T1, step 2 uses time T2, and so forth.

In the algorithm above, steps 1, 2 and 7 will only be run once. For a worst-case evaluation, it should be assumed that step 3 will be run as well. Thus the total amount of time to run steps 1-3 and step 7 is:

The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute ( n + 1 ) times (note that an extra step is required to terminate the for loop, hence n + 1 and not n executions), which will consume T4( n + 1 ) time. The inner loop, on the other hand, is governed by the value of j, which iterates from 1 to i. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body (step 6) consumes T6 time, and the inner loop test (step 5) consumes 2T5 time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body (step 6) consumes 2T6 time, and the inner loop test (step 5) consumes 3T5 time.

Altogether, the total time required to run the inner loop body can be expressed as an arithmetic progression:

which can be factored[10] as

The total time required to run the outer loop test can be evaluated similarly:

which can be factored as

Therefore, the total running time for this algorithm is:

which reduces to

As a rule-of-thumb, one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order. In this example, n2 is the highest-order term, so one can conclude that f(n) = O(n2). Formally this can be proven as follows:

Prove that





Let k be a constant greater than or equal to [T1..T7]



Therefore

A more elegant approach to analyzing this algorithm would be to declare that [T1..T7] are all equal to one unit of time, in a system of units chosen so that one unit is greater than or equal to the actual times for these steps. This would mean that the algorithm's running time breaks down as follows:[11]

Growth rate analysis of other resources[edit]

The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of memory space. As an example, consider the following pseudocode which manages and reallocates memory usage by a program based on the size of a file which that program manages:

while (file still open)
    let n = size of file
    for every 100,000 kilobytes of increase in file size
        double the amount of memory reserved

In this instance, as the file size n increases, memory will be consumed at an exponential growth rate, which is order O(2n). This is an extremely rapid and most likely unmanageable growth rate for consumption of memory resources.

Relevance[edit]

Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless.

Constant factors[edit]

Analysis of algorithms typically focuses on the asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on 32-bit machines 232 = 4 GiB (greater if segmented memory is used) and on 64-bit machines 264 = 16 EiB. Thus given a limited size, an order of growth (time or space) can be replaced by a constant factor, and in this sense all practical algorithms are O(1) for a large enough constant, or for small enough data.

This interpretation is primarily useful for functions that grow extremely slowly: (binary) iterated logarithm (log*) is less than 5 for all practical data (265536 bits); (binary) log-log (log log n) is less than 6 for virtually all practical data (264 bits); and binary log (log n) is less than 64 for virtually all practical data (264 bits). An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have so long as and .

For large data linear or quadratic factors cannot be ignored, but for small data an asymptotically inefficient algorithm may be more efficient. This is particularly used in hybrid algorithms, like Timsort, which use an asymptotically efficient algorithm (here merge sort, with time complexity ), but switch to an asymptotically inefficient algorithm (here insertion sort, with time complexity ) for small data, as the simpler algorithm is faster on small data.

See also[edit]

Notes[edit]

  1. ^ Donald Knuth, Recent News
  2. ^ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co. , section 1.3
  3. ^ Juraj Hromkovič (2004). Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. pp. 177–178. ISBN 978-3-540-14015-3. 
  4. ^ Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. pp. 3–8. ISBN 978-3-540-65431-5. 
  5. ^ Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, p. 20, ISBN 978-3-540-21045-0 
  6. ^ Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. pp. 3–7. ISBN 978-0-89871-187-5. 
  7. ^ Examples of the price of abstraction?, cstheory.stackexchange.com
  8. ^ How To Avoid O-Abuse and Bribes, at the blog "Gödel’s Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick
  9. ^ However, this is not the case with a quantum computer
  10. ^ It can be proven by induction that
  11. ^ This approach, unlike the above approach, neglects the constant time consumed by the loop tests which terminate their respective loops, but it is trivial to prove that such omission does not affect the final result

References[edit]

Disclaimer

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license