analysis of algorithms this article includes a list of references but its sources remain unclear because it has insufficient inline citations please help to improve this article by introducing more precise citations march 2010 learn how and when to remove this template message 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 log2n 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 computational complexity of algorithms that is the amount of time storage andor other resources necessary to execute them usually this involves determining a function that relates the length of an algorithms 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 functions values are small or grow slowly compared to a growth in the size of the input different inputs of the same length may cause the algorithm to have different behavior so best worst and average case descriptions might all be of practical interest when not otherwise specified the function describing the performance of an algorithm is usually an upper bound determined from the worst case inputs to the algorithm the term analysis of algorithms was coined by donald knuth 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 ie to estimate the complexity function for arbitrarily large input big o notation bigomega notation and bigtheta 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 ologn 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 eg turing machine andor 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 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 the uniform cost model also called uniformcost 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 logarithmiccost 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 its only employed when necessary for example in the analysis of arbitraryprecision 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 runtime analysis runtime analysis is a theoretical classification that estimates and anticipates the increase in running time or runtime of an algorithm as its input size usually denoted as n increases runtime 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 algorithms runtime in practice they cannot provide timing data for all infinitely many possible inputs the latter can only be achieved by the theoretical methods of runtime analysis shortcomings of empirical metrics since algorithms are platformindependent ie 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 stateoftheart 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 runtimein nanoseconds computer b runtimein nanoseconds 16 8 100000 63 32 150000 250 125 200000 1000 500 250000 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 inputlist is increased to a sufficient number that conclusion is dramatically demonstrated to be in error n list size computer a runtimein nanoseconds computer b runtimein nanoseconds 16 8 100000 63 32 150000 250 125 200000 1000 500 250000 1000000 500000 500000 4000000 2000000 550000 16000000 8000000 600000 63072 1012 31536 1012 nsor 1 year 1375000 nsor 1375 milliseconds computer a running the linear search program exhibits a linear growth rate the programs runtime is directly proportional to its input size doubling the input size doubles the run time quadrupling the input size quadruples the runtime 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 50000 ns even though computer a is ostensibly a faster machine computer b will inevitably surpass computer a in runtime because its running an algorithm with a much slower growth rate orders of growth big o notation 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 f n displaystyle fn times a positive constant provides an upper bound or limit for the runtime 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 c f n displaystyle ctimes fn this concept is frequently expressed using big o notation for example since the runtime of insertion sort grows quadratically as its input size increases insertion sort can be said to be of order on2 big o notation is a convenient way to express the worstcase scenario for a given algorithm although it can also be used to express the averagecase for example the worstcase scenario for quicksort is on2 but the averagecase runtime is onlogn empirical orders of growth assuming the execution time follows power rule t k na the coefficient a can be found by taking empirical measurements of run time t 1 t 2 displaystyle t1t2 at some problemsize points n 1 n 2 displaystyle n1n2 and calculating t 2 t 1 n 2 n 1 a displaystyle t2t1n2n1a so that a log t 2 t 1 log n 2 n 1 displaystyle alogt2t1logn2n1 in other words this measures the slope of the empirical line on the loglog 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 loglog 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 runtimein nanoseconds local order of growthn computer b runtimein nanoseconds local order of growthn 15 7 100000 65 32 104 150000 028 250 125 101 200000 021 1000 500 100 250000 016 1000000 500000 100 500000 010 4000000 2000000 100 550000 007 16000000 8000000 100 600000 006 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 runtime complexity the runtime complexity for the worstcase 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 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 worstcase evaluation it should be assumed that step 3 will be run as well thus the total amount of time to run steps 13 and step 7 is t 1 t 2 t 3 t 7 displaystyle t1t2t3t7 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 t 6 2 t 6 3 t 6 n 1 t 6 n t 6 displaystyle t62t63t6cdots n1t6nt6 which can be factored as t 6 1 2 3 n 1 n t 6 1 2 n 2 n displaystyle t6left the total time required to run the outer loop test can be evaluated similarly 2 t 5 3 t 5 4 t 5 n 1 t 5 n t 5 n 1 t 5 t 5 2 t 5 3 t 5 4 t 5 n 1 t 5 n t 5 n 1 t 5 t 5 displaystyle beginaligned2t53t54t5cdots n1t5nt5n1t5 t52t53t54t5cdots n1t5nt5n1t5t5endaligned which can be factored as t 5 1 2 3 n 1 n n 1 t 5 1 2 n 2 n t 5 n 1 t 5 t 5 t 5 1 2 n 2 n n t 5 1 2 n 2 3 n t 5 displaystyle beginalignedt5leftt5endaligned therefore the total running time for this algorithm is f n t 1 t 2 t 3 t 7 n 1 t 4 1 2 n 2 n t 6 1 2 n 2 3 n t 5 displaystyle fnt1t2t3t7n1t4leftt5 which reduces to f n 1 2 n 2 n t 6 1 2 n 2 3 n t 5 n 1 t 4 t 1 t 2 t 3 t 7 displaystyle fnleftt5n1t4t1t2t3t7 as a ruleofthumb one can assume that the highestorder term in any given function dominates its rate of growth and thus defines its runtime order in this example n2 is the highestorder term so one can conclude that fn on2 formally this can be proven as follows prove that 1 2 n 2 n t 6 1 2 n 2 3 n t 5 n 1 t 4 t 1 t 2 t 3 t 7 c n 2 n n 0 displaystyle leftt5n1t4t1t2t3t7leq cn2 ngeq n0 1 2 n 2 n t 6 1 2 n 2 3 n t 5 n 1 t 4 t 1 t 2 t 3 t 7 n 2 n t 6 n 2 3 n t 5 n 1 t 4 t 1 t 2 t 3 t 7 for n 0 displaystyle beginalignedleftt5n1t4t1t2t3t7leq n2nt6n23nt5n1t4t1t2t3t7 textfor ngeq 0endaligned let k be a constant greater than or equal to t 6 n 2 n t 5 n 2 3 n n 1 t 4 t 1 t 2 t 3 t 7 k n 2 n k n 2 3 n k n 5 k 2 k n 2 5 k n 5 k 2 k n 2 5 k n 2 5 k n 2 for n 1 12 k n 2 displaystyle beginalignedt6n2nt5n23nn1t4t1t2t3t7leq kn2nkn23nkn5k2kn25kn5kleq 2kn25kn25kn2 textfor ngeq 112kn2endaligned therefore 1 2 n 2 n t 6 1 2 n 2 3 n t 5 n 1 t 4 t 1 t 2 t 3 t 7 c n 2 n n 0 for c 12 k n 0 1 displaystyle leftt5n1t4t1t2t3t7leq cn2ngeq n0text for c12kn01 a more elegant approach to analyzing this algorithm would be to declare that 4 i 1 n i 4 i 1 n n 4 n 2 5 n 2 for n 1 o n 2 displaystyle 4sum i1nileq 4sum i1nn4n2leq 5n2 textfor ngeq 1on2 growth rate analysis of other resources the methodology of runtime 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 100000 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 o2n this is an extremely rapid and most likely unmanageable growth rate for consumption of memory resources relevance algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance in timesensitive 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 analysis of algorithms typically focuses on the asymptotic performance particularly at the elementary level but in practical applications constant factors are important and realworld data is in practice always limited in size the limit is typically the size of addressable memory so on 32bit machines 232 4 gib greater if segmented memory is used and on 64bit 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 o1 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 loglog 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 nonconstant 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 eg one may have k k log log n displaystyle kklog log n so long as k k 6 displaystyle kk6 and n 2 2 6 2 64 displaystyle n226264 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 n log n displaystyle nlog n but switch to an asymptotically inefficient algorithm here insertion sort with time complexity n 2 displaystyle n2 for small data as the simpler algorithm is faster on small data amortized analysis analysis of parallel algorithms asymptotic computational complexity best worst and average case big o notation computational complexity theory master theorem analysis of algorithms npcomplete numerical analysis polynomial time program optimization profiling computer programming scalability smoothed analysis termination analysis the subproblem of checking whether a program will terminate at all time complexity includes table of orders of growth for common algorithms informationbased complexity notes cormen thomas h leiserson charles e rivest ronald l stein clifford 2001 introduction to algorithms chapter 1 foundations second ed cambridge ma mit press and mcgrawhill pp3122 isbn0262032937 sedgewick robert 1998 algorithms in c parts 14 fundamentals data structures sorting searching 3rd ed reading ma addisonwesley professional isbn9780201314526 knuth donald the art of computer programming addisonwesley greene daniel a knuth donald e 1982 mathematics for the analysis of algorithms second ed birkhuser isbn376433102x goldreich oded 2010 computational complexity a conceptual perspective cambridge university press isbn9780521884730 vtemajor fields of computer sciencenote this template roughly follows the 2012 acm computing classification systemhardware printed circuit board peripheral integrated circuit very large scale integration systems on chip socs energy consumption green computing electronic design automation hardware acceleration computer systemsorganization computer architecture embedded system realtime computing dependability networks network architecture network protocol network components network scheduler network performance evaluation network service software organization interpreter middleware virtual machine operating system software quality software notationsand tools programming paradigm programming language compiler domainspecific language modeling language software framework integrated development environment software configuration management software library software repository software development software development process requirements analysis software design software construction software deployment software maintenance programming team opensource model theory of computation model of computation formal language automata theory computational complexity theory logic semantics algorithms algorithm design analysis of algorithms algorithmic efficiency randomized algorithm computational geometry mathematicsof computing discrete mathematics probability statistics mathematical software information theory mathematical analysis numerical analysis informationsystems database management system information storage systems enterprise information system social information systems geographic information system decision support system process control system multimedia information system data mining digital library computing platform digital marketing world wide web information retrieval security cryptography formal methods security services intrusion detection system hardware security network security information security application security humancomputerinteraction interaction design social computing ubiquitous computing visualization accessibility concurrency concurrent computing parallel computing distributed computing multithreading multiprocessing artificialintelligence natural language processing knowledge representation and reasoning computer vision automated planning and scheduling search methodology control method philosophy of artificial intelligence distributed artificial intelligence machine learning supervised learning unsupervised learning reinforcement learning multitask learning crossvalidation graphics animation rendering image manipulation graphics processing unit mixed reality virtual reality image compression solid modeling appliedcomputing ecommerce enterprise software computational mathematics computational physics computational chemistry computational biology computational social science computational engineering computational healthcare digital art electronic publishing cyberwarfare electronic voting video games word processing operations research educational technology document management book category portal wikiproject commons 