Big O Notation –
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
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
• 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)
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
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.
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.
Brute Force Algorithms
Sequential Search (Unordered Array)
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:
• 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.
• Frequently produces
• Some of the produced
algorithms are excessively slow.
• Less constructive and
creative than other techniques.
Here a few brute force
• 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)
What is Big
• 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
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)
Bubble Sort Algorithm Complexity
Comparison Sorting Algorithm
Worst-case and Average-case Time Complexity
Best-case Space Complexity O(n)
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
• 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.
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
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)
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
Tech Blog. (2018). Time
Comparison of Quick Sort, Insertion Sort and Bubble Sort. online Available
Time Comparison of Quick Sort, Insertion Sort and Bubble Sort
Accessed 12 Jan. 2018.
(2018). CmSc360 CH3. online Available at:
Accessed 14 Jan. 2018.