Big O notationNote: a knowledge of Big O notation does not necessarily need to be known by students (or teachers!) for DT 2.44, but it is useful, so read on. DefinitionIn mathematics, computer science, and related fields, big-O notation... ...describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.From http://en.wikipedia.org/wiki/Big_O_notationWhat does this mean? It means that computer algorithms can be approximated by functions and so can be assessed for their efficiency in terms of time to complete. Certain Big O notations are more desirable than others. For instance, searching for an element in an unsorted array of numbers gives O(n), where n is the number of elements. Opposed to this is The Towers of Hanoi which is O(2n). The first is a linear function; in other words the time to search the array is proportional to the number of elements using a linear search - examine the first element, then the next, then the next etc. until a match is found. The worst case scenario is when the element searched for is the very last one. That is why the notation O(n) is used. The function plotted on an x, y graph would give a straight line. The Towers of Hanoi at O(2n) is an example of an exponential function, and when plotted gives an exponential curve. A problem is said to be tractable if it can be shown to have a Big O polynomial representation or better (e.g. linear). This type of function has a Big O notation that takes the form O(nk), where n is the number of iterations of say a loop, and k is a constant. So a simple loop running within a loop coding structure would have a Big O notation of O(n2). A loop within a loop within a loop would have O(n3). As well as linear, polynomial and exponential Big Os, there are also constant O(1), O(n log n), O(log n). The graphic below show some of the O functions plotted as T(n), that is their running time. Click on it to see the larger original image. Note that in the O notation above no constant terms have been placed in front of n. This is because as n increases the constant factors become irrelevant. The following link points to a website that has graphics that demonstrate this well: Algorithmic Complexity and Big-O Notation  Examples of Big O modeled using BYOB 3The following link will take you to a page containing some examples of Big O notation modeled using the BYOB 3 program: Big O examplesOther useful links
|