Complexity Analysis

• A data structure is a scheme of arranging data in computer

memory for efficient manipulation, together with the operations
(algorithms) on the data

• An algorithm is a finite, unambiguous sequence of steps for solving

a problem in a finite amount of time and space.

• A program is an implementation of an algorithm in a particular

programming language.

• The efficient implementation of algorithms is important in

computing, and this depends on suitable data structures.

1
Motivations for Complexity Analysis
• There are often many different algorithms to solve a particular problem.
Thus, it makes sense to develop techniques that allow us to:

compare different algorithms with respect to their “efficiency”

choose the most efficient algorithm for a problem

• The efficiency of any algorithmic solution to a problem is a measure of the:

Time efficiency: the time it takes to execute.

Space efficiency: the space (primary or secondary memory) it uses.

• We will focus on an algorithm’s efficiency with respect to time.

• Often time efficiency is more important than space complexity

More and more space available

time is still a problem

2
 Machine independence
• The evaluation of efficiency should be as machine independent as
possible.

• It is not useful to measure how fast the algorithm runs as this

depends on which particular computer, OS, programming language,
compiler, and kind of inputs that are used in testing. Also the
algorithm has to be implemented.

• Instead,
we count the number of basic operations the algorithm performs.
we calculate how this number depends on the size n of the input.

• A basic operation is an operation which takes a constant amount of

time to execute.

• Hence, the efficiency of an algorithm is the number of basic

operations it performs. This number is a function of the input size n.

3
 Example of Basic Operations:
• Arithmetic operations: *, /, %, +, -

• Boolean operations: &&, ||, !

• Assignment statements of simple data types.

• Reading of primitive types

• writing of a primitive types

• Simple conditional tests: if (x < 12) ...

• method calls (Note: the execution time of a method itself may not be constant)

• a method's return statement.

• Memory Access (includes array indexing)

• We consider an operation such as ++ , += , and *= as consisting of two basic

operations.

• Note: To simplify complexity analysis we shall not consider memory access (fetch or
store) operations

4
 Best, Average, and Worst case complexities
• There are three cases in determining the efficiency of an algorithm:
– Best-case complexity: B(n), the minimum time needed to execute an
algorithm for an input of size n

– Average-case complexity: A(n), the average time needed to execute an

algorithm for an input of size n

– Worst-case complexity: T(n), the maximum time needed to execute an

algorithm for an input of size n

• We are usually interested in the worst case complexity: what are the most
operations that might be performed for a given problem size.
– Easier to compute
– Usually close to the actual running time
– Crucial to real-time systems (e.g. air-traffic control)

• Best case depends on the input

• Average case is often difficult to compute

5
 Best, Average, and Worst case complexities
• Example: Linear Search Complexity

– Best Case : Item found at the beginning: One comparison

– Worst Case : Item found at the end or not found: n comparisons

– Average Case :Item may be found at index 0, or 1, or 2, . . . or n – 1

• Average number of comparisons is: (1 + 2 + . . . + n) / n = (n+1) / 2

6
 Simple Complexity Analysis: Loops
• We start by considering how to count operations in loops.
– We use integer division throughout.

• If the number of iterations of a loop is n.

– The initialization statement is executed one time

– The loop condition is executed n + 1 times.

– Each of the statements in the loop body is executed n times.

– The loop-index update statement is executed n times.

7
 Simple Complexity Analysis: Linear loops
• A linear loop is one in which the loop index is updated by either addition or
subtraction.

• A loop is independent if its index values are independent of an outer loop index.

• Let k and n be non-negative integers such that n >= k

• Then in each of the following independent linear loops:

for(int i = k; i < n; for(int i = n; i > k; i--){

i++){ statement1;
statement1; statement2;
statement2; }
}

• The number of iterations is: (n – k )

• The initialization statement is executed one time.

• The condition is executed (n – k ) + 1 times.

• The update statement is executed (n – k ) times.

• Each of statement1 and statement2 is executed (n – k ) times.

8
Simple Complexity Analysis: Linear loops (cont’d)
• Let k and n be non-negative integers such that n >= k

• Then in each of the following independent linear loops:

for(int i = k; i <= n; for(int i = n; i >= k; i--){

i++){ statement1;
statement1; statement2;
statement2; }
}

• The number of iterations is: (n – k ) + 1

• The initialization statement is executed one time.

• The condition is executed (n – k ) + 2 times.

• The update statement is executed (n – k ) + 1 times.

• Each of statement1 and statement2 is executed (n – k ) + 1 times.

9
Simple Complexity Analysis: Loop Example
• Find the exact number of basic operations in the following program fragment:
double x, y;
x = 2.5 ; y = 3.0;
for(int i = 0; i < n; i++){
a[i] = x * y;
x = 2.5 * x;
y = y + a[i];
}
• There are 2 assignments outside the loop => 2 operations.

• The for loop comprises:

• An assignment i = 0 that is executed once => 1 operation

• A test i < n that is executed n + 1 times => n + 1 operations

• An increment i++ consisting of 2 operations that are executed n times => 2n

operations

• the loop body that has three assignments, two multiplications, and an
addition. Theses 6 operations are executed n times => 6n operations

Thus the total number of basic operations is 6n + 2n + (n + 1) + 3

= 9n + 4

10
 Simple Complexity Analysis: Loop Example
• We analyse the worst and best case complexities of getMax

• Assume that the array is filled with n elements, where n >= 2

public int getMax(int[ ] array, int n){

int currentMax = array[0];
for(int i = 1; i < n; i++){
if(array[i] > currentMax){
currentMax = array[i]; // statement1
}
}
return currentMax;
}

• The loop iterates n - 1 times

• The worst case occurs when the maximum element is the last one in the array; in that
case statement1 will be executed n - 1 times
• Hence we have the worst case time complexity:
T(n) = 2 + n + (n – 1)(2 + 1 + 1) + 1 = 5n – 2

• The best case occurs when the maximum element is the first one in the array; in that
case statement1 will not be executed.
• Hence we have the best case time complexity:
B(n) = 2 + n + (n – 1)(2 + 1) + 1 = 4n + 1
11
 Simple Complexity Analysis: Loop Example
• We analyse the worst and best case complexities of getSum

• Assume that the array is filled with n elements, where n >= 2

public int getSum(int[ ] array, int n){

int sum = 0;
for(int i = 0; i < n; i++){
sum = sum + array[i];
}

return sum;
}

• The loop iterates n times.

• The number of iterations does not depend on the input data

• Hence we have the worst case time complexity is equal to the best-case
time complexity:
T(n) = B(n) = 1 + 1 + (n + 1) + n(2 + 1 + 1) + 1
= 5n + 4

12