Fandom

File Formats Wiki

Analysis of algorithms

261pages on
this wiki
Add New Page
Talk0 Share
Smallwikipedialogo.png Wikipedia has an article related to:
To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or complexity of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

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 of efficient algorithms.

Big O notationEdit

Smallwikipedialogo.png Wikipedia has an article related to:

Big O notation is used to detemine the orders of growth of an algorithm, especially those with iterations or recursions. Generally, big O notation is used in asymptotic analysis of mathematical functions. In computer science, it is used to provide a measure for the best of an algorithm.

The best case is when an algorithm completes with the least operations done. For example, a linear search algorithm is in best case when the item is at the beginning of the list. The worst case is when an algorithm completes with the most possible operations done. For example, a linear search algorithm is in worst case when the item is at the end of the list. The average case is the expected case for any arbitrary input. These cases need not necessarily be not equal.

Frequent big O notations (examples using average-case time complexity) are:

Notation Name Example
O(1) constant Looking up an item in a random access list, adding an item to a linked list
O(log n) logarithmic Looking up an item in a sorted list using binary search
O(n) linear Looking up an item in a linked list
O(n log n) = O(log n!) linearithmic Performing heapsort or merge sort
O(n2) quadratic Performing bubble sort or insertion sort
O(n3) cubic Multiplying two nxn matrices
O(cn), c > 1 exponential Determining if two logical statements are equal using brute force
O(n!) factorial/combinatorial Solving a traveling salesman problem using brute force

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.