PowerPoint Paste Slide 1Big O Notation –Algorithm PerformanceThis presentation has been created tocomprehensively introduce algorithms and Big O Notation to a software company.I will explain what an algorithm is, provideexamples of their use, compare the efficiency of those examples to bruteforcing and discuss how they relate to the application development process.
Data showing the performance of an algorithm using Big O Notation will also beincluded. Slide 2What is an algorithm?Computers perform tasksmade up of algorithms. Algorithms are well-defined procedures that assist inthe discovery of a problem’s solution. They are commonly known to play anactive part in:• Google’s Search Engine• Weather Forecasting• Website Automation• To help find the bestmatches for user searches, Google implemented PageRank into their searchengine. This highly effective algorithm is a key aspect of the search engineand company’s success, as it decides which pages appear first when a userconducts a search.• Weather forecastingalgorithms are used by the Met Office.
They exist to make predictions and modelweather patterns.• To decide productprices, Amazon uses algorithms. It evidently works well, but 2011 saw theautomated computer decisions boost the price of a book to £14 million. (Bbc.co.
uk, 2018) Slide 3Algorithm Implementation• Connecting Algorithm and Code Variant• Using a Suitable Language• Relating to Application Development• Algorithms are abstract recipes for calculationsand are independent of implementation. Code is concrete, and acts as animplementation of the calculations on a compatible platform, in a compatibleprogramming language. Put more simply, programming languages are used toimplement the algorithms that are designed to solve problems and join to createa fully functional program.• There are machine-readable (binary) andhuman-readable languages. Application developers need to know how to code inlow-level languages (can be processed more quickly than high-level languages) tobe able to take maximise a program’s capabilities. A variety of languages areused in modern games for this reason. When computer programs don’t execute asexpected, it is usually because there is a flaw in one or more designedalgorithms.
Beforedeciding on a programming language, algorithms can be written in pseudocode,which is like plain English. The only important rules about pseudocodealgorithms is that they are correct, written in a way that can be understood byprogrammers, have clear intentions and can be implemented on the system it isintended for. Flowcharts can also be used to describe algorithms in avisually simplified manner.•Algorithms make decisions about which order they should do things in by usingcontrol flow. Control flow comprises sequence, selection and iterationelements. Previously completed actions can be repeated or new actions can bestarted upon on the receipt of new information. A sequence is a list ofinstructions that must be followed one after another.
Lookingat control flow in more depth, application development methodologies sharesimilarities with algorithms. They both follow a sequence, utilise iterationsand be influenced by selections. Agile development methodologies includeiterations (short time frames) which include a sequence combining planning,analysis, design, coding, unit testing and user acceptance testing. Programmersare 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 4Brute Force Algorithms• Sequential Search (Unordered Array)• Selection Sort• Bubble SortBrute force, or exhaustivesearch, is a general problem-solving technique or approach that systematicallychallenges every possible solution to a given problem and checks whether theysatisfy the problem’s statement. They are known as exhaustive searches sincethey go through exhaustive effort, and are commonly used to eliminate thenecessity of employing a more intellectual strategy.Strengths and weaknessesof using a brute force approach:Strengths:• Known for simplicity.
• Produces reasonablealgorithms for problems revolving searching, matrix multiplication and stringmatching and other basic computational tasks such as finding the sum andproduct and finding the minimum or maximum value in a list. Brute forcealgorithms typically have rather high time complexities.Weaknesses:• Frequently producesinefficient algorithms.• Some of the producedalgorithms are excessively slow.
• Less constructive andcreative than other techniques.Here a few brute forceapplication examples:• The algorithm associatedwith a sequential search scans a list and compares successive elements with aspecified search key. The list is analysed until a match can or can’t be found.• The algorithm designedspecifically for use with a selection sort scans a list to find the smallestvalue and exchange it with the first value. The list is scanned again and againuntil the smallest value in the list appears at the beginning. • A bubble sort is anotherbrute forcing method. The algorithm compares neighbouring items in a list andexchanges those that don’t appear in order.
(Faculty.simpson.edu, 2018) Slide 5What is BigO Notation?• Mathematical Notation• Classifies Algorithms• Worst-case Scenario• Big O Notation is a mathematical notation, comprisingthe symbols required to write mathematical formulas and equations.• It is a relative representation of an algorithm’sperformance and complexity. Big O Notation classifies algorithms according tohow running time or space requirements increase as the input size increases.Functions are categorised according to their increase rates and dissimilarfunctions that utilise the same rate can be represented with the same Onotation. 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 typicallydescribes and considers the worst outcome that can be projected from a range ofpossibilities.
Slide 6Big ONotation Complexity• O(1) – Ignores size of the input data set.• O(N) – Stays in linear proportion to size ofthe input data set.• O(N2) – Stays directlyproportional to the square of the size of the input data set.• O(2N) – Doubles with each additionto the input data set.• O(log N) – Works in an amount of timeproportional to the logarithm of the input data set.• The algorithm always executes in the same time orspace regardless of the input data set’s size.• The algorithm’s performance grows linearly and indirect proportion to the input data set’s size.• The algorithm’s performance grows in directproportion to the square of the input data set’s size.
This is most common inalgorithms involving nested iterations. Deeply nested iterations result in O(N3),O(N4), O(N5) etc. • The algorithm’s performance growth doubles witheach addition to the input data set. The growth curve is exponential, meaningit starts off shallow and spikes dramatically.• Binary searches are described as O(log N). Theyselect 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 orlower, the same operation will be performed on the respective half of the dataset. The data set will continue to halve until the target item is found or thedata set can no longer be split.
The iterative halving of data sets describedin binary searches produce a growth curve that initially peaks, but then slowlyflattens out. (Rob-bell.net, 2018) Slide 7Bubble Sort Algorithm Complexity• Comparison Sorting Algorithm• Worst-case and Average-case Time ComplexityO(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 comparepairs of adjacent items in a list and swaps those that appear in the wrongorder. Smaller or larger items eventually “bubble” their way to the top of thelist.• Where n is the number of items being sorted. Othersorting algorithms (e.g.
merge, insertion sort) have better performancecomplexities than bubble sort, making it an impractical and inefficient sortingalgorithm when n is large. In otherwords, 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 atn and then n-1 due to the largest value appearing at the end.
The best timecomplexity a bubble sort can have is O(n) which is average. • The space complexity would be O(n) if an extraarray size of n gets allocated. The space complexity is a measure of how muchextra memory the algorithm requires. To increase space complexity, code can beadded to use more memory.
It’s harder to decrease space complexity as codeneeds to be made more efficient. The worst space complexity a bubble sort canhave is O(1) which is classed as excellent. Slide 8Performance of Sort AlgorithmsThe graph shows a comparison of performance for aquick sort, insertion sort and bubble sort.The Y axis represents the time it took the algorithmto sort the data in seconds.The X axis represents the number of items thealgorithm sorted.To conclude, bubble sorts aren’t suitable for manyreal-world applications. Put simply, the time required to perform bubble sorton n increases as the square of n.
(Tech Blog, 2018) BibliographyBbc.co.uk. (2018).
BBCBitesize – GCSE Computer Science – Introducing algorithms – Revision 1.online Available at: https://www.bbc.co.uk/education/guides/z22wwmn/revisionAccessed 12 Jan. 2018.
Rob-bell.net. (2018). Abeginner’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 10Jan. 2018.Tech Blog. (2018). TimeComparison of Quick Sort, Insertion Sort and Bubble Sort. online Availableat:https://vinayakgarg.
wordpress.com/2011/10/25/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.htmAccessed 14 Jan.