Data Structures and Algorithms

Chapter 1 – Algorithm Analysis - 2

Dr. Georges Badr

Time Complexity

 The time complexity of the algorithms can be one of the following:

▪ O(1): Constant
▪ O(log n): Logarithmic
▪ O(n): Linear
▪ O(n*log n): Linearithmic
▪ O(n2): Quadratic
▪ O(n3): Cubic
▪ O(C.n): Exponential
▪ O(n!): Factorial

26
Time Complexity: O(1)

 Time complexity of a function is considered as O(1) if it doesn’t contain

loop, recursion and call to any other non-constant time function

 For example: set of non-recursive and non-loop statements such as the

swap function

 A loop or recursion that runs a constant number of times is also

considered as O(1)

The size is a constant

27
Time Complexity: O(log n)

 Logarithmic time complexities usually apply to algorithms that divide problems

in half every time.

 For instance, let’s say that we want to look for a person in an old phone book. It
has every name sorted alphabetically. There are at least two ways to do it:

▪ Algorithm A
- Start at the beginning of the book and go in order until you find the contact you are looking for. Run-time O(n)

▪ Algorithm B
- Open the book in the middle and check the first name on it.
- If the name that you are looking for is alphabetically bigger, then look to the right. Otherwise, look in the left half,
Run-time O(log n)

28
Time Complexity: Example O(log n)

 The algorithm Binary Search has a complexity of Log n.

At Iteration 1, Length of array = n

𝑛
At Iteration 2, Length of array = 2
𝑛 𝑛
At Iteration 3, Length of array = ( 2 )/2 = 22
𝑛
Therefore, after Iteration k, Length of array = 𝑘
2
Also, we know that after k divisions, the length of array becomes 1
𝑛
Therefore, the length of array = 𝑘 = 1 => n = 2k
2

Applying log function on both sides:

 log2 (n) = log2 (2k)
 log2 (n) = k log2 (2)
As (logx (x) = 1)
Therefore, k = log2 (n)

29
Time Complexity: O(n)

 Linear time complexity O(n) means that as the input grows, the algorithms take
proportionally longer. A function with a linear time complexity has a growth
rate.

 For example:
▪ Get the max/min value in an array
▪ Find a given element in a collection

30
Time Complexity: Example O(n)
1 int findMax(int *arr, int len)

2 {
3 int i = 0;
4 int max = arr[0];
5 for(i=1; i < len; i++)
6 {
7 if(arr[i] >= max)
8 max = arr[i];
9 }
10 return max;
11 }

 If you get the time complexity it would be something like this:

- Line 3-4: 2 operations
- Line 5: a loop of size n
 Line 6-9: 2 operations in the loop ➔ 2 * n
- Line 10: 1 operation

 So, this gets us 2(n) + 3 → By leaving the most significant term, we get n. And finally using the big O notation we get O(n)

31
Time Complexity: O(nlog n)

 Linearithmic time complexity is slightly slower than a linear algorithm but still
much better than a quadratic algorithm.

 Example of linearithmic algorithms:

▪ Efficient sorting algorithms like merge sort, quick sort and others.

32
Time Complexity: Example O(nlogn)

 We have already learned that whenever we divide a number into half

in every step, it can be represented using a logarithmic function (log
n)

 Also, we perform a single step operation to find out the middle of

any subarray, i.e O(1)

 Finally, to merge the n elements of the

subarrays, the time required is O(n)

 Hence, the total time is O(n*log n)

33
Time Complexity: O(n2)

 A function with a quadratic time complexity has a growth rate n2.

 Here are some examples of O(n2) quadratic algorithms:

▪ Check if an array has duplicated values
▪ Sorting elements in an array using bubble sort, insertion sort and selection sort.

34
Time Complexity: O(n2)
Find duplications in a non sorted array O(n2)
for(i=0→n)
for(j=i→n)
if(array[i]==array[j])

Find duplication in a sorted array: O(n)

for(i=0→n)
if(array[i]==array[i+1])

Sort the array then search for duplication

Merge sort: O(nlogn) + find duplicates: O(n)
O(nlogn + n) = O(nlogn) < O(n2)

35
Time Complexity: O(nc)

 Polynomial running is represented as O(nc) when c>1. As you already saw, two
inner loops translate to O(n2) since it has to go through the array twice in most
cases.

 Are three nested loops cubic? In most cases, yes!

 Usually, we want to stay away from polynomial running times (quadratic, cubic,
O(nc)) since they take longer to compute as the input grows fast.

 However, they are not the worst.

36
Time Complexity: O(Cn)

 Exponential running time means that the calculations performed by an

algorithm double every time as the input grows.

 Example of exponential runtime algorithms:

▪ Power set: finding all the subsets on a set
▪ Recursive Fibonacci

37
Time Complexity: Example O(2n)

 Let’s imagine you are buying a pizza. The store has many toppings that you can
choose from like pepperoni, mushrooms, bacon, and pineapple.

 Let’s call each topping A, B, C, D. What are your choices?

 You can select:

▪ no topping
▪ one topping
▪ a combination of two
▪ a combination of three
▪ all of them.

38
Time Complexity: Example O(2n)

 If you plot n and f(n), you will notice that it would be exactly like the function
2n.

 This algorithm has a running time of O(2n).

39
Time Complexity: O(n!)

 Factorial is the multiplication of all positive integer numbers less than itself.

 As you might guess, you want to stay away if possible from algorithms that have
this running time.

 Example of O(n!) factorial runtime algorithms:

▪ Permutations of a string
▪ Brute-force search

40
Time Complexity: Example O(n!)

41
All running complexities graphs

42
Exercises

1st loop: O (N)

2nd loop: O (M)

Code: O (N+M)
if M = N → O (2N) = O (N) = O (n)

43
Exercises

1st fragment: 2 nested loops: O (N*N) = O (n2)

2nd fragment: 1 loop : O(N) = O(n)
Total: O (n2 + n) = O (n2)

44
Exercises

N I J number of times the statements are executed

4 0 4321 4 -> N
1 432 3 -> N-1
2 43 2 -> N-2
3 4 1 -> N-3
Total number of times = 4 + 3 + 2 + 1
= N + N-1 + N-2 + N-3 + N-4 + …. + N-k + ... + 1
𝑁∗(𝑁+1) (𝑁2 +1)
= =
2 2
(𝑁2 +1)
O( ) = O (N2)
2

45
Exercises
Exercise 2:

for(int i = 0; i < n; i += 2) n/2

{
for(int j = 0; j < 6; j++) 6
{
for(int k = 0; k < n; k++) n
{
for(int m = 0; m < 5; m++) 5
{ ___________
// operations; O(n/2 * 6 * n * 5)
} O(30 * n2 / 2)
} O(n2)
}
}

46
Exercises
Exercise 3:

for(int i = 1; i <= n; i *= 2)
{
// statements;
}

n = 1000
i = 1 2 4 8 16 32 64 128 256 512 1024
2^10 = 1024
O(log n)

2k=n
Log(2k) = log (n)
K log(2) = log (n)
K = log(n)

47
Exercises
Exercise 4:

for(int i = 0; i < n; i++) O(n)

{
for(int j = 0; j < n; j++)
{
// operations;
O(n)
} O(n * 2n)
for(int k = 0; k < n; k++) O(n+n) O(n2)
{
// operations; O(n)
}
}

48
Exercises
Exercise 5:

for(int i = n; i > 1; i = i / 2)
{
// statements;
}

n = 1024
i = 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2 (i>1)

10 operations
Log2(1024) = 10
➔ O(log(n))

49
Exercises
Exercise 5:

int fct(int n) {
int sum = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
sum++;
} }
return sum;
}

Calculate
1- Res = fct (10)
2- Complexity?

Res = 100

Complexity: O (n2)
50
Exercises
Exercise 6:
int fct(int n) {
int sum = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(j < n/2) {
for(int k = 0; k < n; k++) {
for(int m = 0; m < n; m++) {
sum++;
} } } } }
return sum;
} n = 10
Calculate 10 (for the 1st loop)
1- Res = fct (10) *
2- Complexity? nd
5 (2 loop = condition+2 loops)
*
Res = 5000
10 (3rd loop) * 10 (4th loop)
Complexity = O(n4)
= 5000
51
Exercises
Exercise 7:
int fct(int n) {
int sum = 0;
for(int i = 0; i < n/2; i+=2) {
for(int j = 0; j < 10; j++) {
for(int k = 0; k < n; k++) {
for(int m = 0; m < 10; m++) {
sum++;
} } } }
return sum;
}

Calculate
1- Res = fct (10)
2- Complexity?

Res = 3000
Complexity = O(n/4 * 1 * n * 1) = O( n2/4) = O (n2)
52
Exercises
Exercise 8: Exercise 9:
int fct(int n) { int fct(int n) {
int sum = 10; int sum = 10;
for(int i = 0; i < 2 * n; i++) { for(int i = 0; i < 2*n; i++) {
for(int j = 0; j < n; j++) { for(int j = 0; j < n; j++) {
sum++; sum++;
return sum; break;
} }
} }
} return sum;
}
Calculate
1- Res = fct (10) Calculate
2- Complexity? 1- Res = fct (10)
2- Complexity?

Res = 11 Res = 30
O(1) O(2n) =O(n)
53