Time Complexity Analysis
Time Complexity Analysis
Embedded Files
The time complexity analysis of an algorithm is the determination of how many times the basic instruction(s) of the algorithm execute depending on the input size. The basic instruction(s) is usually selected to be the operation that:
is needed to solve the problem
is the most time consuming
is the most frequently used
Examples of basic instructions/operations can be given as 'each pass in a while loop' or 'comparison instruction'. In general, we do not include the control structure (like increment and compare the index) in the basic operations. There is no hard and fast rule for choosing the basic operation. It is largely a matter of judgment and experience.
When we analyze an algorithm for time complexity, we identify the function, g(n), that defines how many times the basic instruction(s) is repeated for an input size of n. The g(n) function can be put into categories such as BigO, Omega, and Theta. It is important to note that BigO, Omega, and Theta define sets.
BigO: “Big O” puts an asymptotic upper bound on a function. For a given complexity function f (n), O(f(n)) is the set of complexity functions g(n) for which there exists some positive real constant c and some nonnegative integer N such that for all n ≥ N,
g(n) ≤ c × f(n)
g(n) є O(f(n))
Ex: 4n^2 <=c × n^2, 4n^2 є O(n^2)
Omega: “Omega” puts an asymptotic lower bound on a function. For a given complexity function f(n), Ω(f (n)) is the set of complexity functions g (n) for which there exists some positive real constant c and some nonnegative integer N such that, for all n ≥ N,
g(n) ≥ c × f(n)
g(n) є Ω(f(n))
Theta: For a given complexity function f(n), θ(f(n)) = O(f(n)) ∩ Ω(f(n)) This means that θ(f(n)) is the set of complexity functions g(n) for which there exist some positive real constants c and d and some nonnegative integer N such that, for all n ≥ N,
c × f(n) ≤ g(n) ≤ d × f(n)
g(n) є θ(f(n))
The figure below illustrates a) BigO b) Omega and c) Theta functions.
Some exemplary functions of the sets O (n2 ) ,Ω (n2 ), and Θ (n2 ) are shown in the figure above.
Example Pseudocode for BigO sets
O(1)
The instructions execute approximately the same number of times as the input size. O(1) describes an algorithm that will always execute at the same time (or space) regardless of the size of the input data set.
In the following code, the return statement (basic operation) always gets executed once:
bool IsFirstElementNull(IList<string> elements)
{
return elements[0] == null;
}
O(n)
O(n)
O(n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
In the following code, the if statement (basic operation) is executed proportionally to the size of the input (elements list).
bool ContainsValue(IList<string> elements, string value)
{
for each (var element in elements)
{
if (element == value) return true;
}
return false;
}
O(n^2): Represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set.
O(n^2): Represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set.
What kind of code would have O(n^3), O(n^4) complexities?
What kind of code would have O(n^3), O(n^4) complexities?
In the following code, the innermost if statement(s) (basic operation) is executed proportionally to the size^2 of the input (elements list).
bool ContainsDuplicates(IList<string> elements)
{
for (var outer = 0; outer < elements.Count; outer++)
{
for (var inner = 0; inner < elements.Count; inner++)
{
// Don't compare with self
if (outer == inner) continue;
if (elements[outer] == elements[inner]) return true;
}
}
return false;
}
O(2^n): Denotes an algorithm whose growth doubles with each addition to the input data set.
O(2^n): Denotes an algorithm whose growth doubles with each addition to the input data set.
In the following code, the return statement (basic operation) is executed proportionally to the 2^value of the input.
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
O(log n): The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increases.
O(log n): The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increases.
For example: If an input data set containing 10 items takes one second to complete, then a data set containing 100 items takes two seconds and a data set containing 1000 items will take three seconds.
For example: If an input data set containing 10 items takes one second to complete, then a data set containing 100 items takes two seconds and a data set containing 1000 items will take three seconds.
In the following code, the inner instructions of the loop (for example the if statement is executed proportionally to the log(size of the array).
function binary_search(Arrray A, integer n, integer searchKey)
{
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < searchKey then
L := m + 1
else if A[m] > searchKey then
R := m − 1
else:
return m
return unsuccessful
}
Page updated
Google Sites
Report abuse