2 of 25

Learning Objectives

Understand that algorithms can be characterised by their complexity
Understand the time-efficiency of algorithms
Understand the space-efficiency of algorithms

Success Criteria

Explain the difference between efficient algorithm and that of non-efficiency.
Create more space-efficiency program to solve up five equations as minimum.
Explain the reason for efficiency for space.

3 of 25

What is an algorithm ?

An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.

4 of 25

Properties of algorithms:

Input from a specified set,

Output from a specified set (solution),

Definiteness of every step in the computation,

Correctness of output for every possible input,

Finiteness of the number of calculation steps,

Effectiveness of each calculation step and

Generality for a class of problems.

5 of 25

Complexity of Algorithms

Computational complexity of an algorithm

Measures how economical of the algorithm is with time and space

Time complexity of an algorithm

indicates how fast an algorithm runs

Space complexity of an algorithm

indicates how much memory an algorithm needs

6 of 25

Efficiency

Time
Size of program code
Size of input and output
Amount of memory needed during program running.

7 of 25

Big-O Notation - O(n)

A notation that expresses computing time (complexity) as the term in a function that increases most rapidly relative to the size of a problem

A special notation to compare algorithms

Differences ?

https://youtu.be/-Eiw_-v__Vo

8 of 25

Big-O Notation - O(n)

9 of 25

Big-O Analysis

O(1)	bounded time	Assigning a value to the i th element in an array of N elements Algorithms that successively cut the amount of data to be processed in half at each step typically fall into this category
O(log₂N)	logarithmic time	Finding a value in a list of sorted elements using the binary search algorithm
O(N)	linear time	Printing all the elements in a list of N elements
O(N log₂N)	applying a logarithmic algorithm N times	The better sorting algorithms, such as Quicksort, Heapsort, and Mergesort
O(N²)	applying a linear algorithm N times	Most simple sorting algorithms
O(2^N)	exponential time
O(n!)	factorial time	The traveling salesperson graph algorithm

10 of 25

Cheat Sheet

bigocheatsheet.com

11 of 25

Revise Big O

12 of 25

Different algorithms for same problem

Algorithms for the same problem can be based on very different ideas and can solve the problem with dramatically different speeds.

Algorithm SumNaturalNumbers(n)

//Implements sum of first n natural numbers

//Input: An integer n >= 1

//Output: Sum

Sum = 0

For i = 1 to n

Do Sum = Sum + i

Return Sum

Algorithm SumNaturalNumbersByFormula(n)

//Implements sum of first n natural numbers

//Input: An integer n >= 1

//Output: Sum

Sum = n * (n+1)/2

Return Sum

13 of 25

Complexity of

Bubble vs Insertion

14 of 25

Insert An Element

Let's have a quick read

https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/analysis-of-insertion-sort

15 of 25

Insert An Element

public static void insert(int[] a, int n, int x)

{

// insert t into a[0:i-1]

int j;

for (j = i - 1; j >= 0 && x < a[j]; j--)

a[j + 1] = a[j];

a[j + 1] = x;

}

16 of 25

Insertion Sort

for (int i = 1; i < a.length; i++)

{

// insert a[i] into a[0:i-1]

insert(a, i, a[i]);

}

17 of 25

Insertion Sort – Algorithm Complexity

How many compares are done?

1+2+…+(n-1), O(n2) worst case
(n-1)* 1 , O(n) best case

How many element shifts are done?

1+2+...+(n-1), O(n2) worst case
0 , O(1) best case

18 of 25

Worst Case Complexity

Bubble:

#Compares: O(n²)
#Swaps: O(n²)

Insertion

#Compares: O(n²)
#Shifts: O(n²)

19 of 25

Bubble Sort / Сортировка пузырьком

Start – Unsorted

Compare, swap (0, 1)

Compare, swap (1, 2)

Compare, no swap

Compare, noswap

Compare, swap (4, 5)

99 in position

20 of 25

Bubble Sort

Pass 2
swap (0, 1)
no swap
no swap
swap (3, 4)
21 in position

21 of 25

Bubble Sort

Pass 3
no swap
no swap
swap (2, 3)
12 in position, Pass 4
no swap
swap (1, 2)
8 in position, Pass 5
swap (1, 2)
Done

22 of 25

Bubble Sort – Algorithm Complexity

Time consuming operations

compares, swaps.

#Compares

a FOR loop embedded inside a while loop
(n-1)+(n-2)+(n-3) …+1 , or O(n²)

#Swaps

inside a conditional -> #swaps data dependent !!
Best Case 0, or O(1)
Worst Case (n-1)+(n-2)+(n-3) …+1 , or O(n²)

Время-ресурсоемкие операции

сравнивает, заменяет.

#Сравнение

цикл FOR встроен внутри цикла WHILE
(n-1)+(n-2)+(n-3) …+1 , or O(n²)

#Замена

внутри условного -> #замена зависит от данных!!
В лучшем случае 0, или O(1)
В худшем случае (n-1)+(n-2)+(n-3) …+1 , or O(n²)

23 of 25

Insertion Sort / Сортировка вставками

24 of 25

Faster Computer Vs Better Algorithm

Algorithmic improvement more useful

than hardware improvement.

E.g. 2ⁿ to n³