Complexity of Algorithms and Big-O Notation
Delve into the world of algorithm analysis and complexity with discussions on what algorithms are, how to measure their complexity, and the significance of Big-O notation in comparing algorithm performance as the input size grows. Explore asymptotic notations, growth rates of functions, and essential reviews in complexity analysis exercises.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
COMP 352 SUMMER 2018 Tutorial Session 1 1
ANALYSISAND COMPLEXITYOF ALGORITHMS: What is Algorithms? What do we mean by Complexity ? How to measure Complexity ? 2
ANALYSISAND COMPLEXITYOF ALGORITHMS Algorithm is a sequence of computational steps that transform the input into the output. Analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. The complexity of an algorithm is the cost, measured in running time, or storage, or whatever units are relevant, of using the algorithm to solve one of those problems. 3
BIG-O Big-O notation is a relative representation of the performance or complexity of an algorithm. Big O is just a way to "Express" yourself in a common way to compare different algorithms, How the running time of the algorithm grows when the size of the input grows ? "How much time / space does it take to run the code? 4
THESEVENFUNCTIONSALONGWITHTHEIR CORRESPONDINGGROWTHRATE: 6
IMPORTANTREVIEWS: To compute the sum of all integers from i to n: Properties of: Logarithms Exponentials 8
IMPORTANTREVIEWS: Geometric series formula: Sum of terms: 9
COMPLEXITY ANALYSIS EXERCISE 1 Consider the following code, n is data size int i = 1; while (i <= n) { System.out.println("*"); i = 2 * i; } What is the big-O time complexity in terms of n? Show all necessary steps. 10
COMPLEXITY ANALYSIS EXERCISE 2 Consider the following code, n is data size While(n >0){ For (int j =0; j < n; j++) System.out.println( * ); n = n / 2; } What is the big-O time complexity in terms of n? Show all necessary steps. 11
COMPLEXITY ANALYSIS EXERCISE 3 Prove that the running time T(n) = n2+ 42n + 7 is O(n2) 12
COMPLEXITY ANALYSIS EXERCISE 4 Show that if d(n) is O(f(n)) and e(n) is O(g(n)) , then the product d(n)e(n) is O(f(n)g(n)) 13
COMPLEXITY ANALYSIS EXERCISE 5 14
COMPLEXITY ANALYSIS EXERCISE 6 Prove that running time T(n)= n3+ 20n is (n2) 15
COMPLEXITY ANALYSIS EXERCISE 7 16
SOMEINTERESTINGLINKS A cheat sheet to find complexity of loops: https://www.geeksforgeeks.org/analysis-of- algorithms-set-4-analysis-of-loops/ To demonstrate big oh notation with limits (slide 12): http://130.216.33.163/compsci220s1c/lectures/2013S 1C/Part1/220-04.pdf Another example to prove big Oh: http://www.cs.utsa.edu/~bylander/cs3233/big-oh.pdf Big oh cheatsheet: http://bigocheatsheet.com
