PowerPoint Paste

Slide 1

Big O Notation –

Algorithm Performance

This presentation has been created to

comprehensively introduce algorithms and Big O Notation to a software company.

I will explain what an algorithm is, provide

examples of their use, compare the efficiency of those examples to brute

forcing and discuss how they relate to the application development process.

Data showing the performance of an algorithm using Big O Notation will also be

included.

Slide 2

What is an algorithm?

Computers perform tasks

made up of algorithms. Algorithms are well-defined procedures that assist in

the discovery of a problem’s solution. They are commonly known to play an

active part in:

• Google’s Search Engine

• Weather Forecasting

• Website Automation

• To help find the best

matches for user searches, Google implemented PageRank into their search

engine. This highly effective algorithm is a key aspect of the search engine

and company’s success, as it decides which pages appear first when a user

conducts a search.

• Weather forecasting

algorithms are used by the Met Office. They exist to make predictions and model

weather patterns.

• To decide product

prices, Amazon uses algorithms. It evidently works well, but 2011 saw the

automated computer decisions boost the price of a book to £14 million. (Bbc.co.uk, 2018)

Slide 3

Algorithm Implementation

•

Connecting Algorithm and Code Variant

•

Using a Suitable Language

•

Relating to Application Development

• Algorithms are abstract recipes for calculations

and are independent of implementation. Code is concrete, and acts as an

implementation of the calculations on a compatible platform, in a compatible

programming language. Put more simply, programming languages are used to

implement the algorithms that are designed to solve problems and join to create

a fully functional program.

• There are machine-readable (binary) and

human-readable languages. Application developers need to know how to code in

low-level languages (can be processed more quickly than high-level languages) to

be able to take maximise a program’s capabilities. A variety of languages are

used in modern games for this reason. When computer programs don’t execute as

expected, it is usually because there is a flaw in one or more designed

algorithms. Before

deciding on a programming language, algorithms can be written in pseudocode,

which is like plain English. The only important rules about pseudocode

algorithms is that they are correct, written in a way that can be understood by

programmers, have clear intentions and can be implemented on the system it is

intended for. Flowcharts can also be used to describe algorithms in a

visually simplified manner.

•

Algorithms make decisions about which order they should do things in by using

control flow. Control flow comprises sequence, selection and iteration

elements. Previously completed actions can be repeated or new actions can be

started upon on the receipt of new information. A sequence is a list of

instructions that must be followed one after another.

Looking

at control flow in more depth, application development methodologies share

similarities with algorithms. They both follow a sequence, utilise iterations

and be influenced by selections. Agile development methodologies include

iterations (short time frames) which include a sequence combining planning,

analysis, design, coding, unit testing and user acceptance testing. Programmers

are also able to revisit iterations or parts of the sequence if, for example,

they start coding and realise that something in the design stage is flawed.

Slide 4

Brute Force Algorithms

•

Sequential Search (Unordered Array)

•

Selection Sort

•

Bubble Sort

Brute force, or exhaustive

search, is a general problem-solving technique or approach that systematically

challenges every possible solution to a given problem and checks whether they

satisfy the problem’s statement. They are known as exhaustive searches since

they go through exhaustive effort, and are commonly used to eliminate the

necessity of employing a more intellectual strategy.

Strengths and weaknesses

of using a brute force approach:

Strengths:

• Known for simplicity.

• Produces reasonable

algorithms for problems revolving searching, matrix multiplication and string

matching and other basic computational tasks such as finding the sum and

product and finding the minimum or maximum value in a list. Brute force

algorithms typically have rather high time complexities.

Weaknesses:

• Frequently produces

inefficient algorithms.

• Some of the produced

algorithms are excessively slow.

• Less constructive and

creative than other techniques.

Here a few brute force

application examples:

• The algorithm associated

with a sequential search scans a list and compares successive elements with a

specified search key. The list is analysed until a match can or can’t be found.

• The algorithm designed

specifically for use with a selection sort scans a list to find the smallest

value and exchange it with the first value. The list is scanned again and again

until the smallest value in the list appears at the beginning.

• A bubble sort is another

brute forcing method. The algorithm compares neighbouring items in a list and

exchanges those that don’t appear in order. (Faculty.simpson.edu, 2018)

Slide 5

What is Big

O Notation?

•

Mathematical Notation

•

Classifies Algorithms

•

Worst-case Scenario

• Big O Notation is a mathematical notation, comprising

the symbols required to write mathematical formulas and equations.

• It is a relative representation of an algorithm’s

performance and complexity. Big O Notation classifies algorithms according to

how running time or space requirements increase as the input size increases.

Functions are categorised according to their increase rates and dissimilar

functions that utilise the same rate can be represented with the same O

notation. As a result, the ‘O’ in Big O Notation refers to the mentioned increases,

as the growth rate of a function is also known as ‘order of the function’.

• More specifically, Big O Notation typically

describes and considers the worst outcome that can be projected from a range of

possibilities.

Slide 6

Big O

Notation Complexity

•

O(1) – Ignores size of the input data set.

•

O(N) – Stays in linear proportion to size of

the input data set.

•

O(N2) – Stays directly

proportional to the square of the size of the input data set.

•

O(2N) – Doubles with each addition

to the input data set.

•

O(log N) – Works in an amount of time

proportional to the logarithm of the input data set.

• The algorithm always executes in the same time or

space regardless of the input data set’s size.

• The algorithm’s performance grows linearly and in

direct proportion to the input data set’s size.

• The algorithm’s performance grows in direct

proportion to the square of the input data set’s size. This is most common in

algorithms involving nested iterations. Deeply nested iterations result in O(N3),

O(N4), O(N5) etc.

• The algorithm’s performance growth doubles with

each addition to the input data set. The growth curve is exponential, meaning

it starts off shallow and spikes dramatically.

• Binary searches are described as O(log N). They

select the median (middle) item of a data set and compare it to a target item.

If the items match, the search is complete. If the target item is higher or

lower, the same operation will be performed on the respective half of the data

set. The data set will continue to halve until the target item is found or the

data set can no longer be split. The iterative halving of data sets described

in binary searches produce a growth curve that initially peaks, but then slowly

flattens out. (Rob-bell.net, 2018)

Slide 7

Bubble Sort Algorithm Complexity

•

Comparison Sorting Algorithm

•

Worst-case and Average-case Time Complexity

O(n2)

•

Best-case Space Complexity O(n)

->

Unsorted list

->

After Iteration 1

->

After Iteration 2

->

And so on…

• Also known as sinking sorts, bubble sorts compare

pairs of adjacent items in a list and swaps those that appear in the wrong

order. Smaller or larger items eventually “bubble” their way to the top of the

list.

• Where n is the number of items being sorted. Other

sorting algorithms (e.g. merge, insertion sort) have better performance

complexities than bubble sort, making it an impractical and inefficient sorting

algorithm when n is large. In other

words, bubble sorts should be avoided when working with large data sets. O(N2)

is the worst-case complexity as the array could be sorted but in the wrong

(descending) order. In this instance, the first iteration would have to look at

n and then n-1 due to the largest value appearing at the end. The best time

complexity a bubble sort can have is O(n) which is average.

• The space complexity would be O(n) if an extra

array size of n gets allocated. The space complexity is a measure of how much

extra memory the algorithm requires. To increase space complexity, code can be

added to use more memory. It’s harder to decrease space complexity as code

needs to be made more efficient. The worst space complexity a bubble sort can

have is O(1) which is classed as excellent.

Slide 8

Performance of Sort Algorithms

The graph shows a comparison of performance for a

quick sort, insertion sort and bubble sort.

The Y axis represents the time it took the algorithm

to sort the data in seconds.

The X axis represents the number of items the

algorithm sorted.

To conclude, bubble sorts aren’t suitable for many

real-world applications. Put simply, the time required to perform bubble sort

on n increases as the square of n. (Tech Blog, 2018)

Bibliography

Bbc.co.uk. (2018). BBC

Bitesize – GCSE Computer Science – Introducing algorithms – Revision 1.

online Available at: https://www.bbc.co.uk/education/guides/z22wwmn/revision

Accessed 12 Jan. 2018.

Rob-bell.net. (2018). A

beginner’s guide to Big O notation – Rob Bell. online Available at:

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ Accessed 10

Jan. 2018.

Tech Blog. (2018). Time

Comparison of Quick Sort, Insertion Sort and Bubble Sort. online Available

at:

Time Comparison of Quick Sort, Insertion Sort and Bubble Sort

Accessed 12 Jan. 2018.

Faculty.simpson.edu.

(2018). CmSc360 CH3. online Available at:

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Levitin/L05-BruteForce.htm

Accessed 14 Jan. 2018.