Complexity
Objective: Learn to analyze the time complexity of an algorithm.
A task (problem) can be solved by different algorithms.
The questions are:

Whether there is an optimum algorithm?

Which algorithm is the optimum?
Criteria for choosing an algorithm:

correctness

easy to understand, implement and maintain

clear and well documented

efficient: space and time
To evaluate an algorithm efficiency, often we are interested in the rate of growth of the time or space required to solve larger instances of a kind of problem.

We usually associate with a problem an integer, called the size of the problem, which measures the quantity of input data.

The time needed by an algorithm expressed as a function of the size of a problem is called the time complexity of the algorithm.

The limiting behavior of the time complexity when the size increases is called the asymptotic time complexity.
Analogous definition can be made for the space complexity and asymptotic space complexity.
It is the asymptotic complexity of an algorithm that ultimately determines the size of a problem that can be solved by the algorithm.
T(n) , the time complexity function, is the measure of time taken by a program or an algorithm on any input of size n.
We can think T(n) as the number of basic statements or operations executed by the program. However, we are not interested in the exact values of the function T(n), but rather in the rate of growth, or order of growth, of the running time. In many cases, we would like to find the upper bound of the complexity. We therefore consider only the leading term of a formula (e.g., aN^{2} ), since the lowerorder terms are relatively insignificant for large N.
Regarding an asymptotic upper bound, if an algorithm processes input of size N in time c*g(n) for some constant c, then, we say that the time complexity of the algorithm is O(g(n)).  Onotation.
Onotation is used to hide:

average number of machine instructions a particular compiler generates

average number of machine instructions a particular machine executes per second
This helps to ignore computer and compiler related constants but it also allows us to make some simplifying assumptions.
Running time of an algorithm depends on two things:
Size of input: Example: Add n numbers
If n = 5 then the following part of a program requires 17 units of time, T (n) = 5
int sum = 0;
for (int i = 1; i<=5; i++) {
sum = sum + i;
};
As n increases we expect the running time to increase.
If n is very small then even an inefficient algorithm will not have a long running time.
Particular input:

even if we consider the inputs having the same size, the number of operations performed by an algorithm may depend on the particular input.
Example: An algorithm for alphabetizing a list of names may do very little work if only a few of the names are out of order, but it may have to do much more work on the list that is very scrambled.
Andrea Penny
David David
Cathy Evelyn
Evelyn Cathy
Penny Andrea
Therefore, the number of steps an algorithm takes depends on not just the size of input values, but also the particular types of input values.
For this reason, there are three different cases for running times:

Best case running time  the least running time on any input among all inputs of size n.

Average case running time – the average running time of the program over all inputs of size n.

more realistic but harder to compute

Worst case running time  the maximum running time on any input among all inputs of size n.
We usually concentrate on finding only the worstcase running time, that is, the longest running time for any input of size n. Its reasons are:

the worst case is an upper bound,

the worst case occurs fairly often for some algorithms,

the average case is sometimes roughly as bad as the worst case.
The averagecase running time of an algorithm is interested in some situations.
Example: Suppose that we pick a program whose running time is as follows:
T (n) = c(n+ 1)^{2} = cn^{2} + 2cn + c
We say that T(n) is O(n^{2}).^{ }This gives us a way of seeing how the value n, the size of input, affects the algorithm.

Constant factors do not matter
Ex. T (n) = 6n, we say that T(n) is O(n).

Low order terms do not matter and can be ignored
T (n) = 4n^{5} + 3n^{4}..., we say that T(n) = O(n^{5}).
Common Order Classes of algorithms:
O(1) Constant
O(log n) logarithmic
O (n) Linear
O(n log n) n log n
O(n^{2}) quadratic
O(n^{3}) cubic
O(2^{n}) exponential
An algorithm in O (1) is said to have a constant time complexity. This kind of algorithm is independent of the problem size. Ex., an algorithm that prints one element of an array has the running time which is independent of the size of the array.
Operation rules:
Assume T_{1} (n) is O(f(n)), and T_{2}(n) is O(g(n))
,where f(n) and g(n) are functions defined on n, T_{1}and T_{2} are running times of algorithm 1 and algorithm 2 respectively, then T_{1}+ T_{2} is O(max(f(n), g(n))).
Example: T_{1} = O(n^{2}), T_{2 }= O(n^{3})
T_{2} will dominate, hence T_{1} + T_{2 }= T_{2 }= O (n^{3})
Assume T_{1} (n) is O(f (n)) and T_{2}(n) is O(g (n)),
then T_{1} * T_{2 }is T_{1}(f (n) *g (n)).
if f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) is O(h(n)).
Analysis of instructions to determine a running time:

Simple statements are O(1).
Assignment, addition, multiplication, or accessing an array takes constant amount of time O(1).
2. Conditional statement
if ( condition ) {
True part statements;
}
else {
False part statements;
}
Overall time for a conditional statement is the time taken to evaluate the condition plus maximum time for true part or false part.

if the time to evaluate the condition is O(1) then that can be ignored
If the if statement is a nested statement:
if (condition) {
statements;
}
else if (condition ){
statements;
}
…
else {statements;
}
Assuming that there are no method calls in the conditions. The running time for the if is the running time of the part that takes the most time.
3. for loops

running time is the production result of :

the limits specified in the for statement
(the limit of the loop indicates the number of times the loop will be executed)

the time to run the body of the loop
Ex. To get the overall time complexity for loops:

get the number of times the loop is to be executed

n (= upper limitlower limit + 1)
for (int i = 1; i== n; i++) {statements;}

Obtain the amount of time spent in one iteration which
includes:
Steps performed once:

time to initialize the loop index is 1 (constant time O(1)).

time to test the loop index the first time is 1 (constant time O(1)).
Steps performed the number of times the loop is executed:

time to test the loop index is 1 (constant time O(1))

the time to increment the loop index is 1 (constant time O(1)).
In general these constant times can be dropped by the rule of summation.
Example 1: for loop

int a;

int sum = 0;

for (int i= 1; i = = n; i++) {

a = i*2;

sum = sum + a;

}
The loop is executed n times, and the running time of the body of the loop is 2. Therefore, T(n) = 2n, the time complexity for the loop is O(n).
Share with your friends: 