Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Install
Faster access than browser!
 

Analysis of algorithms

+ Save concept

In computer science, the analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them. [1]

80 relations: Abstract machine, Algorithm, Algorithmic efficiency, Amortized analysis, Analysis of parallel algorithms, Arbitrary-precision arithmetic, Arithmetic progression, Asymptotic analysis, Asymptotic computational complexity, Benchmark (computing), Best, worst and average case, Big O notation, Binary search algorithm, Cambridge University Press, Collation, Computation, Computational complexity, Computational complexity theory, Computational problem, Computer, Computer file, Computer program, Computer science, Control flow, Cross-platform, Cryptography, Deterministic system, Donald Knuth, DSPACE, DTIME, Elegance, Empirical evidence, Exponential growth, Factorization, Function (mathematics), Hybrid algorithm, Implementation, Information, Information-based complexity, Insertion sort, Instruction set architecture, Introduction to Algorithms, Iterated logarithm, Iteration, Kilobyte, Linear search, Linearity, List (abstract data type), Logarithm, Log–log plot, ..., Master theorem (analysis of algorithms), Mathematical induction, Memory segmentation, Merge sort, Model of computation, Nanosecond, NP-completeness, Numerical analysis, Operating system, Profiling (computer programming), Program optimization, Programming language, Pseudocode, Quadratic growth, Quantum computing, Quicksort, Reduction (mathematics), Robert Tarjan, Rule of thumb, Scalability, Smoothed analysis, Springer Science+Business Media, System resource, Termination analysis, The Art of Computer Programming, Time complexity, Timsort, Triviality (mathematics), Turing machine, Upper and lower bounds. Expand index (30 more) »

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.

New!!: Analysis of algorithms and Abstract machine · See more »

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Analysis of algorithms and Algorithm · See more »

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.

New!!: Analysis of algorithms and Algorithmic efficiency · See more »

Amortized analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute.

New!!: Analysis of algorithms and Amortized analysis · See more »

Analysis of parallel algorithms

This article discusses the analysis of parallel algorithms.

New!!: Analysis of algorithms and Analysis of parallel algorithms · See more »

Arbitrary-precision arithmetic

In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple-precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system.

New!!: Analysis of algorithms and Arbitrary-precision arithmetic · See more »

Arithmetic progression

In mathematics, an arithmetic progression (AP) or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant.

New!!: Analysis of algorithms and Arithmetic progression · See more »

Asymptotic analysis

In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.

New!!: Analysis of algorithms and Asymptotic analysis · See more »

Asymptotic computational complexity

In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.

New!!: Analysis of algorithms and Asymptotic computational complexity · See more »

Benchmark (computing)

In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it.

New!!: Analysis of algorithms and Benchmark (computing) · See more »

Best, worst and average case

In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.

New!!: Analysis of algorithms and Best, worst and average case · See more »

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

New!!: Analysis of algorithms and Big O notation · See more »

Binary search algorithm

In computer science, binary search, also known as half-interval search,logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

New!!: Analysis of algorithms and Binary search algorithm · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: Analysis of algorithms and Cambridge University Press · See more »

Collation

Collation is the assembly of written information into a standard order.

New!!: Analysis of algorithms and Collation · See more »

Computation

Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.

New!!: Analysis of algorithms and Computation · See more »

Computational complexity

In computer science, the computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.

New!!: Analysis of algorithms and Computational complexity · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Analysis of algorithms and Computational complexity theory · See more »

Computational problem

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

New!!: Analysis of algorithms and Computational problem · See more »

Computer

A computer is a device that can be instructed to carry out sequences of arithmetic or logical operations automatically via computer programming.

New!!: Analysis of algorithms and Computer · See more »

Computer file

A computer file is a computer resource for recording data discretely in a computer storage device.

New!!: Analysis of algorithms and Computer file · See more »

Computer program

A computer program is a collection of instructions for performing a specific task that is designed to solve a specific class of problems.

New!!: Analysis of algorithms and Computer program · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Analysis of algorithms and Computer science · See more »

Control flow

In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated.

New!!: Analysis of algorithms and Control flow · See more »

Cross-platform

In computing, cross-platform software (also multi-platform software or platform-independent software) is computer software that is implemented on multiple computing platforms.

New!!: Analysis of algorithms and Cross-platform · See more »

Cryptography

Cryptography or cryptology (from κρυπτός|translit.

New!!: Analysis of algorithms and Cryptography · See more »

Deterministic system

In mathematics, computer science and physics, a deterministic system is a system in which no randomness is involved in the development of future states of the system.

New!!: Analysis of algorithms and Deterministic system · See more »

Donald Knuth

Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.

New!!: Analysis of algorithms and Donald Knuth · See more »

DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine.

New!!: Analysis of algorithms and DSPACE · See more »

DTIME

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine.

New!!: Analysis of algorithms and DTIME · See more »

Elegance

Elegance is beauty that shows unusual effectiveness and simplicity.

New!!: Analysis of algorithms and Elegance · See more »

Empirical evidence

Empirical evidence, also known as sensory experience, is the information received by means of the senses, particularly by observation and documentation of patterns and behavior through experimentation.

New!!: Analysis of algorithms and Empirical evidence · See more »

Exponential growth

Exponential growth is exhibited when the rate of change—the change per instant or unit of time—of the value of a mathematical function is proportional to the function's current value, resulting in its value at any time being an exponential function of time, i.e., a function in which the time value is the exponent.

New!!: Analysis of algorithms and Exponential growth · See more »

Factorization

In mathematics, factorization (also factorisation in some forms of British English) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind.

New!!: Analysis of algorithms and Factorization · See more »

Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

New!!: Analysis of algorithms and Function (mathematics) · See more »

Hybrid algorithm

A hybrid algorithm is an algorithm that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm.

New!!: Analysis of algorithms and Hybrid algorithm · See more »

Implementation

Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.

New!!: Analysis of algorithms and Implementation · See more »

Information

Information is any entity or form that provides the answer to a question of some kind or resolves uncertainty.

New!!: Analysis of algorithms and Information · See more »

Information-based complexity

Information-based complexity (IBC) studies optimal algorithms and computational complexity for the continuous problems which arise in physical science, economics, engineering, and mathematical finance.

New!!: Analysis of algorithms and Information-based complexity · See more »

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

New!!: Analysis of algorithms and Insertion sort · See more »

Instruction set architecture

An instruction set architecture (ISA) is an abstract model of a computer.

New!!: Analysis of algorithms and Instruction set architecture · See more »

Introduction to Algorithms

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

New!!: Analysis of algorithms and Introduction to Algorithms · See more »

Iterated logarithm

In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

New!!: Analysis of algorithms and Iterated logarithm · See more »

Iteration

Iteration is the act of repeating a process, to generate a (possibly unbounded) sequence of outcomes, with the aim of approaching a desired goal, target or result.

New!!: Analysis of algorithms and Iteration · See more »

Kilobyte

The kilobyte is a multiple of the unit byte for digital information.

New!!: Analysis of algorithms and Kilobyte · See more »

Linear search

In computer science, linear search or sequential search is a method for finding a target value within a list.

New!!: Analysis of algorithms and Linear search · See more »

Linearity

Linearity is the property of a mathematical relationship or function which means that it can be graphically represented as a straight line.

New!!: Analysis of algorithms and Linearity · See more »

List (abstract data type)

In computer science, a list or sequence is an abstract data type that represents a countable number of ordered values, where the same value may occur more than once.

New!!: Analysis of algorithms and List (abstract data type) · See more »

Logarithm

In mathematics, the logarithm is the inverse function to exponentiation.

New!!: Analysis of algorithms and Logarithm · See more »

Log–log plot

In science and engineering, a log–log graph or log–log plot is a two-dimensional graph of numerical data that uses logarithmic scales on both the horizontal and vertical axes.

New!!: Analysis of algorithms and Log–log plot · See more »

Master theorem (analysis of algorithms)

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.

New!!: Analysis of algorithms and Master theorem (analysis of algorithms) · See more »

Mathematical induction

Mathematical induction is a mathematical proof technique.

New!!: Analysis of algorithms and Mathematical induction · See more »

Memory segmentation

Memory segmentation is the division of a computer's primary memory into segments or sections.

New!!: Analysis of algorithms and Memory segmentation · See more »

Merge sort

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm.

New!!: Analysis of algorithms and Merge sort · See more »

Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how a set of outputs are computed given a set of inputs.

New!!: Analysis of algorithms and Model of computation · See more »

Nanosecond

A nanosecond (ns) is an SI unit of time equal to one thousand-millionth of a second (or one billionth of a second), that is, 1/1,000,000,000 of a second, or 10 seconds.

New!!: Analysis of algorithms and Nanosecond · See more »

NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Analysis of algorithms and NP-completeness · See more »

Numerical analysis

Numerical analysis is the study of algorithms that use numerical approximation (as opposed to general symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics).

New!!: Analysis of algorithms and Numerical analysis · See more »

Operating system

An operating system (OS) is system software that manages computer hardware and software resources and provides common services for computer programs.

New!!: Analysis of algorithms and Operating system · See more »

Profiling (computer programming)

In software engineering, profiling ("program profiling", "software profiling") is a form of dynamic program analysis that measures, for example, the space (memory) or time complexity of a program, the usage of particular instructions, or the frequency and duration of function calls.

New!!: Analysis of algorithms and Profiling (computer programming) · See more »

Program optimization

In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources.

New!!: Analysis of algorithms and Program optimization · See more »

Programming language

A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.

New!!: Analysis of algorithms and Programming language · See more »

Pseudocode

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

New!!: Analysis of algorithms and Pseudocode · See more »

Quadratic growth

In mathematics, a function or sequence is said to exhibit quadratic growth when its values are proportional to the square of the function argument or sequence position.

New!!: Analysis of algorithms and Quadratic growth · See more »

Quantum computing

Quantum computing is computing using quantum-mechanical phenomena, such as superposition and entanglement.

New!!: Analysis of algorithms and Quantum computing · See more »

Quicksort

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

New!!: Analysis of algorithms and Quicksort · See more »

Reduction (mathematics)

In mathematics, reduction refers to the rewriting of an expression into a simpler form.

New!!: Analysis of algorithms and Reduction (mathematics) · See more »

Robert Tarjan

Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician.

New!!: Analysis of algorithms and Robert Tarjan · See more »

Rule of thumb

The English phrase rule of thumb refers to a principle with broad application that is not intended to be strictly accurate or reliable for every situation.

New!!: Analysis of algorithms and Rule of thumb · See more »

Scalability

Scalability is the capability of a system, network, or process to handle a growing amount of work, or its potential to be enlarged to accommodate that growth.

New!!: Analysis of algorithms and Scalability · See more »

Smoothed analysis

Smoothed analysis is a way of measuring the complexity of an algorithm.

New!!: Analysis of algorithms and Smoothed analysis · See more »

Springer Science+Business Media

Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.

New!!: Analysis of algorithms and Springer Science+Business Media · See more »

System resource

In computing, a system resource, or simply resource, is any physical or virtual component of limited availability within a computer system.

New!!: Analysis of algorithms and System resource · See more »

Termination analysis

In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate.

New!!: Analysis of algorithms and Termination analysis · See more »

The Art of Computer Programming

The Art of Computer Programming (sometimes known by its initials TAOCP) is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.

New!!: Analysis of algorithms and The Art of Computer Programming · See more »

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

New!!: Analysis of algorithms and Time complexity · See more »

Timsort

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

New!!: Analysis of algorithms and Timsort · See more »

Triviality (mathematics)

In mathematics, the adjective trivial is frequently used for objects (for example, groups or topological spaces) that have a very simple structure.

New!!: Analysis of algorithms and Triviality (mathematics) · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: Analysis of algorithms and Turing machine · See more »

Upper and lower bounds

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set (K, ≤) is an element of K which is greater than or equal to every element of S. The term lower bound is defined dually as an element of K which is less than or equal to every element of S. A set with an upper bound is said to be bounded from above by that bound, a set with a lower bound is said to be bounded from below by that bound.

New!!: Analysis of algorithms and Upper and lower bounds · See more »

Redirects here:

"uniform cost model", Algorithm analysis, Complexity analysis, Computational expense, Computationally expensive, Cost model (computer science), Design and analysis of algorithms, Logarithmic cost model, Problem size, Run-time analysis, Runtime analysis, Time/space complexity, Uniform cost model.

References

[1] https://en.wikipedia.org/wiki/Analysis_of_algorithms

OutgoingIncoming
Hey! We are on Facebook now! »