Efficiency of Algorithms
and O(n) notation
Computer Science
https://b2a.kz/Dgr
Learning Objectives
Success Criteria
What is an algorithm ?
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.
Complexity of Algorithms
Computational complexity of an algorithm
Time complexity of an algorithm
Space complexity of an algorithm
Efficiency
Big-O Notation - O(n)
Differences ?
Big-O Notation - O(n)
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(log2N) | 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 log2N) | applying a logarithmic algorithm N times | The better sorting algorithms, such as Quicksort, Heapsort, and Mergesort |
O(N2) | applying a linear algorithm N times | Most simple sorting algorithms |
O(2N) | exponential time | |
O(n!) | factorial time | The traveling salesperson graph algorithm |
Cheat Sheet
bigocheatsheet.com
Revise Big O
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
Complexity of
Bubble vs Insertion
Insert An Element
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;
}
Insertion Sort
for (int i = 1; i < a.length; i++)
{
// insert a[i] into a[0:i-1]
insert(a, i, a[i]);
}
Insertion Sort – Algorithm Complexity
Worst Case Complexity
Bubble Sort / Сортировка пузырьком
Bubble Sort
Bubble Sort
Bubble Sort – Algorithm Complexity
Insertion Sort / Сортировка вставками
Faster Computer Vs Better Algorithm
Algorithmic improvement more useful
than hardware improvement.
E.g. 2n to n3
Extra resource