Big-O Notation in Algorithms
Big-O notation is a crucial method to describe algorithm complexity in terms of time or space. This notation provides an estimate of the steps needed for algorithm completion and helps in analyzing algorithm efficiency. Explore examples and rules to grasp the implications of different complexities like O(1), O(n), O(n^2), and comparisons of increase speed between different notations. Gain insights into how choosing algorithms with smaller Big-O notations can lead to greater efficiency, especially for handling large-scale data.
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
Definition Big-O Notation is the most widely used method which describes algorithm complexity: the execution time required or the space used in memory or in disk by an algorithm Big O notation is used describe the rough estimate of the number of steps to complete the algorithm
Assume that doSomething() takes C steps to complete Part 1: - It does doSomething() - So it takes constant C steps - C is independent to the parameter n - When the time complexity is independent to the parameter, big-O notation is O(1) Part 2: - It does doSomething() n times - Each time it takes C steps - So in total it takes n*C steps to complete - Then big-O is n*O(1) due to Part1 - Important rule, a*O(n) = O(an) - So the time complexity is n*O(1) is O(n) Part 3: - It has two loops. Inner one is same as Part2. Outer loop does Part2 n times - So the time complexity is n*O(n)=O(n2) Part 4: - It takes exactly 1 step to return - So time complexity O(1) void exampleBigO(int n) { // part 1 doSomething(); // part 2 for(int i=0; i<n; i++) doSomething(); // part 3 for(int i=0; i<n; i++) for(int j=0; j<n; j++) doSomething(); // part 4 return; }
Big-O for time complexity So total time complexity for exampleBigO(int n) function is equal to sum of time complexities of all parts: O(1)+ O(n)+O(n2)+O(1) If the parameter n becomes a very large number Then Part 1 and Part 4 can be ignored because they are not dependent to the parameter n and spend very less time comparing to Part 2 and Part 3 When the parameter n becomes extremely large number, then Part 2 also can be ignored So when add up big-O notations, the notation with slower increase speed could be ignored by the notation with faster increase speed. So result big-O notation for exampleBigO() is O(n2)
Rules summary for big-O O(1) * O(n) = O(n) O(n) * O(n) = O(n2) O(1) + O(n) = O(n) O(n) + O(n2) = O(n2) O(1) + O(n) + O(n2) = O(n2) Comparison of increase speed: O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n2)
Comparison of Algorithms Often algorithm with smaller big-O notation is more efficient But it may not be correct for small scale of data But this rule will be efficient for very large number of data Because computer science is always dealing with large scale of data this rule is applicable
big-O space complexity It is easier to understand using big-O to estimate space complexity as it is more concrete When number of elements of an array is constant C and which is independent to n, then the space complexity for using the array is Cn which is O(n)*O(C) = O(n)*O(1) =O(n) When comparing different algorithms, often compare how much extra space complexity is needed to solve the problem The algorithm that needs an extra array of size n is not as good as the one which only needs two variables O(1) is more efficient then O(n)
