1 of 25

Efficiency of Algorithms

and O(n) notation

Computer Science

https://b2a.kz/Dgr

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(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

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

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(n2)
    • #Swaps: O(n2)

  • Insertion
    • #Compares: O(n2)
    • #Shifts: O(n2)

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(n2)
  • #Swaps
    • inside a conditional -> #swaps data dependent !!
    • Best Case 0, or O(1)
    • Worst Case (n-1)+(n-2)+(n-3) …+1 , or O(n2)
  • Время-ресурсоемкие операции
    • сравнивает, заменяет.
  • #Сравнение
    • цикл FOR встроен внутри цикла WHILE
    • (n-1)+(n-2)+(n-3) …+1 , or O(n2)
  • #Замена
    • внутри условного -> #замена зависит от данных!!
    • В лучшем случае 0, или O(1)
    • В худшем случае (n-1)+(n-2)+(n-3) …+1 , or O(n2)

23 of 25

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

24 of 25

Faster Computer Vs Better Algorithm

Algorithmic improvement more useful

than hardware improvement.

E.g. 2n to n3

25 of 25

Extra resource