algorithmic efficiency in computer science algorithmic efficiency is a property of an algorithm which relates to the number of computational resources used by the algorithm an algorithm must be analyzed to determine its resource usage and the efficiency of an algorithm can be measured based on usage of different resources algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process for maximum efficiency we wish to minimize resource usage however different resources such as time and space complexity cannot be compared directly so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered most important for example bubble sort and timsort are both algorithms to sort a list of items from smallest to largest bubble sort sorts the list in time proportional to the number of elements squared o n 2 displaystyle scriptstyle mathcal oleftn2right see big o notation but only requires a small amount of extra memory which is constant with respect to the length of the list o 1 textstyle scriptstyle mathcal oleft1right timsort sorts the list in time linearithmic proportional to a quantity times its logarithm in the lists length o n log n textstyle scriptstyle mathcal oleftnlog nright but has a space requirement linear in the length of the list o n textstyle scriptstyle mathcal oleftnright if large lists must be sorted at high speed for a given application timsort is a better choice however if minimizing the memory footprint of the sorting is more important bubble sort is a better choice note that this article is not about optimization which is discussed in program optimization optimizing compiler loop optimization object code optimizer etc background the importance of efficiency with respect to time was emphasised by ada lovelace in 1843 as applying to charles babbages mechanical analytical engine in almost every computation a great variety of arrangements for the succession of the processes is possible and various considerations must influence the selections amongst them for the purposes of a calculating engine one essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation early electronic computers were severely limited both by the speed of operations and the amount of memory available in some cases it was realized that there was a spacetime tradeoff whereby a task could be handled either by using a fast algorithm which used quite a lot of working memory or by using a slower algorithm which used very little working memory the engineering tradeoff was then to use the fastest algorithm which would fit in the available memory modern computers are significantly faster than the early computers and have a much larger amount of memory available gigabytes instead of kilobytes nevertheless donald knuth emphasised that efficiency is still an important consideration in established engineering disciplines a 12 improvement easily obtained is never considered marginal and i believe the same viewpoint should prevail in software engineering overview an algorithm is considered efficient if its resource consumption also known as computational cost is at or below some acceptable level roughly speaking acceptable means it will run in a reasonable amount of time or space on an available computer typically as a function of the size of the input since the 1950s computers have seen dramatic increases in both the available computational power and in the available amount of memory so current acceptable levels would have been unacceptable even 10 years ago in fact thanks to the approximate doubling of computer power ever 2 years tasks that are acceptably efficient on modern smartphones and embedded systems may have been unacceptably inefficient for industrial servers 10 years ago computer manufacturers frequently bring out new models often with higher performance software costs can be quite high so in some cases the simplest and cheapest way of getting higher performance might be to just buy a faster computer provided it is compatible with an existing computer there are many ways in which the resources used by an algorithm can be measured the two most common measures are speed and memory usage other measures could include transmission speed temporary disk usage longterm disk usage power consumption total cost of ownership response time to external stimuli etc many of these measures depend on the size of the input to the algorithm ie the amount of data to be processed they might also depend on the way in which the data is arranged for example some sorting algorithms perform poorly on data which is already sorted or which is sorted in reverse order in practice there are other factors which can affect the efficiency of an algorithm such as requirements for accuracy andor reliability as detailed below the way in which an algorithm is implemented can also have a significant effect on actual efficiency though many aspects of this relate to optimization issues theoretical analysis in the theoretical analysis of algorithms the normal practice is to estimate their complexity in the asymptotic sense the most commonly used notation to describe resource consumption or complexity is donald knuths big o notation representing the complexity of an algorithm as a function of the size of the input n textstyle scriptstyle n big o notation is an asymptotic measure of function complexity where f n o g n textstyle scriptstyle fleftnrightmathcal oleftgleftnrightright roughly means the time requirement for an algorithm is proportional to g n displaystyle scriptstyle gleftnright omitting lowerorder terms that contribute less than g n displaystyle scriptstyle gleftnright to the growth of the function as n displaystyle scriptstyle n grows arbitrarily large this estimate may be misleading when n textstyle scriptstyle n is small but is generally sufficiently accurate when n textstyle scriptstyle n is large as the notation is asymptotic for example bubble sort may be faster than merge sort when only a few items are to be sorted however either implementation is likely to meet performance requirements for a small list typically programmers are interested in algorithms that scale efficiently to large input sizes and merge sort is preferred over bubble sort for lists of length encountered in most dataintensive programs some examples of big o notation applied to algorithms asymptotic time complexity include notation name examples o 1 displaystyle mathcal o1 constant finding the median from a sorted list of measurements using a constantsize lookup table using a suitable hash function for looking up an item o log n displaystyle mathcal olog n logarithmic finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a binomial heap o n displaystyle mathcal on linear finding an item in an unsorted list or a malformed tree worst case or in an unsorted array adding two nbit integers by ripple carry o n log n displaystyle mathcal onlog n linearithmic loglinear or quasilinear performing a fast fourier transform heapsort quicksort best and average case or merge sort o n 2 displaystyle mathcal on2 quadratic multiplying two ndigit numbers by a simple algorithm bubble sort worst case or naive implementation shell sort quicksort worst case selection sort or insertion sort o c n c 1 displaystyle mathcal ocnc1 exponential finding the optimal nonapproximate solution to the travelling salesman problem using dynamic programming determining if two logical statements are equivalent using bruteforce search benchmarking measuring performance for new versions of software or to provide comparisons with competitive systems benchmarks are sometimes used which assist with gauging an algorithms relative performance if a new sort algorithm is produced for example it can be compared with its predecessors to ensure that at least it is efficient as before with known data taking into consideration any functional improvements benchmarks can be used by customers when comparing various products from alternative suppliers to estimate which product will best suit their specific requirements in terms of functionality and performance for example in the mainframe world certain proprietary sort products from independent software companies such as syncsort compete with products from the major suppliers such as ibm for speed some benchmarks provide opportunities for producing an analysis comparing the relative speed of various compiled and interpreted languages for example and the computer language benchmarks game compares the performance of implementations of typical programming problems in several programming languages even creating do it yourself benchmarks can demonstrate the relative performance of different programming languages using a variety of user specified criteria this is quite simple as a nine language performance roundup by christopher w cowellshah demonstrates by example implementation concerns implementation issues can also have an effect on efficiency such as the choice of programming language or the way in which the algorithm is actually coded see the articles on justintime compilation and interpreted languages there are other factors which may affect time or space issues but which may be outside of a programmers control these include data alignment data granularity cache locality cache coherency garbage collection instructionlevel parallelism multithreading at either a hardware or software level simultaneous multitasking and subroutine calls some processors have capabilities for vector processing which allow a single instruction to operate on multiple operands it may or may not be easy for a programmer or compiler to use these capabilities algorithms designed for sequential processing may need to be completely redesigned to make use of parallel processing or they could be easily reconfigured as parallel and distributed computing grow in importance in the late 2010s more investments are being made into efficient highlevel application programming interfaces for parallel and distributed computing systems such as cuda tensorflow hadoop openmp and mpi another problem which can arise in programming is that processors compatible with the same instruction set such as x8664 or arm may implement an instruction in different ways so that instructions which are relatively fast on some models may be relatively slow on other models this often presents challenges to optimizing compilers which must have a great amount of knowledge of the specific cpu and other hardware available on the compilation target to best optimize a program for performance in the extreme case a compiler may be forced to emulate instructions not supported on a compilation target platform forcing it to generate code or link an external library call to produce a result that is otherwise incomputable on that platform even if it is natively supported and more efficient in hardware on other platforms this is often the case in embedded systems with respect to floatingpoint arithmetic where small and lowpower microcontrollers often lack hardware support for floatingpoint arithmetic and thus require computationally expensive software routines to produce floating point calculations measures of resource usage measures are normally expressed as a function of the size of the input n displaystyle scriptstyle n the two most common measures are time how long does the algorithm take to complete space how much working memory typically ram is needed by the algorithm this has two aspects the amount of memory needed by the code auxiliary space usage and the amount of memory needed for the data on which the code operates intrinsic space usage for computers whose power is supplied by a battery eg laptops and smartphones or for very longlarge calculations eg supercomputers other measures of interest are direct power consumption power needed directly to operate the computer indirect power consumption power needed for cooling lighting etc as of 2018 power consumption is growing as an important metric for computational tasks of all types and at all scales ranging from embedded internet of things devices to systemonchip devices to server farms this trend is often referred to as green computing less common measures of computational efficiency may also be relevant in some cases transmission size bandwidth could be a limiting factor data compression can be used to reduce the amount of data to be transmitted displaying a picture or image eg google logo can result in transmitting tens of thousands of bytes 48k in this case compared with transmitting six bytes for the text google this is important for io bound computing tasks external space space needed on a disk or other external memory device this could be for temporary storage while the algorithm is being carried out or it could be longterm storage needed to be carried forward for future reference response time latency this is particularly relevant in a realtime application when the computer system must respond quickly to some external event total cost of ownership particularly if a computer is dedicated to one particular algorithm time theory analyze the algorithm typically using time complexity analysis to get an estimate of the running time as a function of the size of the input data the result is normally expressed using big o notation this is useful for comparing algorithms especially when a large amount of data is to be processed more detailed estimates are needed to compare algorithm performance when the amount of data is small although this is likely to be of less importance algorithms which include parallel processing may be more difficult to analyze practice use a benchmark to time the use of an algorithm many programming languages have an available function which provides cpu time usage for longrunning algorithms the elapsed time could also be of interest results should generally be averaged over several tests runbased profiling can be very sensitive to hardware configuration and the possibility of other programs or tasks running at the same time in a multiprocessing and multiprogramming environment this sort of test also depends heavily on the selection of a particular programming language compiler and compiler options so algorithms being compared must all be implemented under the same conditions space this section is concerned with the use of memory resources registers cache ram virtual memory secondary memory while the algorithm is being executed as for time analysis above analyze the algorithm typically using space complexity analysis to get an estimate of the runtime memory needed as a function as the size of the input data the result is normally expressed using big o notation there are up to four aspects of memory usage to consider the amount of memory needed to hold the code for the algorithm the amount of memory needed for the input data the amount of memory needed for any output data some algorithms such as sorting often rearrange the input data and dont need any additional space for output data this property is referred to as inplace operation the amount of memory needed as working space during the calculation this includes local variables and any stack space needed by routines called during a calculation this stack space can be significant for algorithms which use recursive techniques early electronic computers and early home computers had relatively small amounts of working memory for example the 1949 electronic delay storage automatic calculator edsac had a maximum working memory of 1024 17bit words while the 1980 sinclair zx80 came initially with 1024 8bit bytes of working memory in the late 2010s it is typical for personal computers to have between 4 and 32 gb of ram an increase of over 300 million times as much memory caching and memory hierarchy further information memory hierarchy current computers can have relatively large amounts of memory possibly gigabytes so having to squeeze an algorithm into a confined amount of memory is much less of a problem than it used to be but the presence of four different categories of memory can be significant processor registers the fastest of computer memory technologies with the least amount of storage space most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache main memory and virtual memory if needed on a processor core there are typically on the order of hundreds of bytes or fewer of register availability although a register file may contain more physical registers than architectural registers defined in the instruction set architecture cache memory is the second fastest and second smallest memory available in the memory hierarchy caches are present in cpus gpus hard disk drives and external peripherals and are typically implemented in static ram memory caches are multileveled lower levels are larger slower and typically shared between processor cores in multicore processors in order to process operands in cache memory a processing unit must fetch the data from the cache perform the operation in registers and write the data back to the cache this operates at speeds comparable about 210 times slower with the cpu or gpus arithmetic logic unit or floatingpoint unit if in the l1 cache it is about 10 times slower if there is an l1 cache miss and it must be retrieved from and written to the l2 cache and a further 10 times slower if there is an l2 cache miss and it must be retrieved from an l3 cache if present main physical memory is most often implemented in dynamic ram dram the main memory is much larger typically gigabytes compared to 8 megabytes than an l3 cpu cache with read and write latencies typically 10100 times slower ram is increasingly implemented onchip of processors as cpu or gpu memory virtual memory is most often implemented in terms of secondary storage such as a hard disk and is an extension to the memory hierarchy that has much larger storage space but much larger latency typically around 1000 times slower than a cache miss for a value in ram cache misses from main memory are called page faults and incur huge performance penalties on programs an algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory which in turn will be very much faster than an algorithm which has to resort to virtual memory because of this cache replacement policies are extremely important to highperformance computing as are cacheaware programming and data alignment to further complicate the issue some systems have up to three levels of cache memory with varying effective speeds different systems will have different amounts of these various types of memory so the effect of algorithm memory needs can vary greatly from one system to another in the early days of electronic computing if an algorithm and its data wouldnt fit in main memory then the algorithm couldnt be used nowadays the use of virtual memory appears to provide lots of memory but at the cost of performance if an algorithm and its data will fit in cache memory then very high speed can be obtained in this case minimizing space will also help minimize time this is called the principle of locality and can be subdivided into locality of reference spatial locality and temporal locality an algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well criticism of the current state of programming david may frs a british computer scientist and currently professor of computer science at university of bristol and founder and cto of xmos semiconductor believes one of the problems is that there is a reliance on moores law to solve inefficiencies he has advanced an alternative to moores law mays law stated as follows software efficiency halves every 18 months compensating moores law may goes on to state in ubiquitous systems halving the instructions executed can double the battery life and big data sets bring big opportunities for better software and algorithms reducing the number of operations from n x n to n x logn has a dramatic effect when n is large for n 30 billion this change is as good as 50 years of technology improvements software author adam n rosenburg in his blog the failure of the digital computer has described the current state of programming as nearing the software event horizon alluding to the fictitious shoe event horizon described by douglas adams in his hitchhikers guide to the galaxy book he estimates there has been a 70db factor loss of productivity or 9999999 percent of its ability to deliver the goods since the 1980swhen arthur c clarke compared the reality of computing in 2001 to the computer hal 9000 in his book 2001 a space odyssey he pointed out how wonderfully small and powerful computers were but how disappointing computer programming had become competitions for the best algorithms the following competitions invite entries for the best algorithms based on some arbitrary criteria decided by the judges wired magazine analysis of algorithmshow to determine the resources needed by an algorithm arithmetic codinga form of variablelength entropy encoding for efficient data compression associative arraya data structure that can be made more efficient using patricia trees or judy arrays benchmarka method for measuring comparative execution times in defined cases best worst and average caseconsiderations for estimating execution times in three scenarios binary search algorithma simple and efficient technique for searching sorted arrays branch tablea technique for reducing instruction pathlength size of machine code and often also memory comparison of programming paradigmsparadigm specific performance considerations compiler optimizationcompilerderived optimization computational complexity of mathematical operations computational complexity theory computer performancecomputer hardware metrics data compressionreducing transmission bandwidth and disk storage database indexa data structure that improves the speed of data retrieval operations on a database table entropy encodingencoding data efficiently using frequency of occurrence of strings as a criterion for substitution garbage collectionautomatic freeing of memory after use green computinga move to implement greener technologies consuming less resources huffman algorithman algorithm for efficient data encoding improving managed code performancemicrosoft msdn library locality of referencefor avoidance of caching delays caused by nonlocal memory access loop optimization memory management optimization computer science performance analysismethods of measuring actual performance of an algorithm at runtime realtime computingfurther examples of timecritical applications runtime analysisestimation of expected runtimes and an algorithms scalability simultaneous multithreading sorting algorithm comparison of algorithms speculative execution or eager execution branch prediction superthreading hyperthreading threaded codesimilar to virtual method table or branch table virtual method tablebranch table with dynamically assigned pointers for dispatching wikibooks has a book on the topic of optimizing code for speed animation of the boyermoore algorithm java applet how algorithms shape our world a ted conference talk by kevin slavin misconceptions about algorithmic efficiency in highschools 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 