title

Big O Notations

description

Get the Code Here: http://goo.gl/Y3UTH
MY UDEMY COURSES ARE 87.5% OFF TIL December 19th ($9.99) ONE IS FREE
➡️ Python Data Science Series for $9.99 : Highest Rated & Largest Python Udemy Course + 56 Hrs + 200 Videos + Data Science https://bit.ly/Master_Python_41
➡️ C++ Programming Bootcamp Series for $9.99 : Over 23 Hrs + 53 Videos + Quizzes + Graded Assignments + New Videos Every Month https://bit.ly/C_Course_41
➡️ FREE 15 hour Golang Course!!! : https://bit.ly/go-tutorial3
Welcome to my Big O Notations tutorial. Big O notations are used to measure how well a computer algorithm scales as the amount of data involved increases. It isn't however always a measure of speed as you'll see.
This is a rough overview of Big O and I hope to simplify it rather than get into all of the complexity. I'll specifically cover the following O(1), O(N), O(N^2), O(log N) and O(N log N). Between the video and code below I hope everything is completely understandable.
MY UDEMY COURSES ARE 87.5% OFF TILL MAY 20th
►► New C++ Programming Bootcamp Series for $9.99 : http://bit.ly/C_Course
Over 20 Hrs + 52 Videos + Quizzes + Graded Assignments + New Videos Every Month
►► Python Programming Bootcamp Series for $9.99 : http://bit.ly/Master_Python
Highest Rated Python Udemy Course + 48 Hrs + 199 Videos + Data Science

detail

{'title': 'Big O Notations', 'heatmap': [{'end': 542.086, 'start': 528.382, 'weight': 0.765}, {'end': 722.005, 'start': 686.547, 'weight': 0.884}, {'end': 989.514, 'start': 972.141, 'weight': 0.71}], 'summary': 'Tutorial on big o notations covers understanding the concept, basics, and explanation of o(1) and o(n) notations with code examples. it also discusses algorithm performance, efficiency of binary search, and quicksort implementation, providing a comprehensive overview of big o notation and its practical applications.', 'chapters': [{'end': 57.875, 'segs': [{'end': 57.875, 'src': 'embed', 'start': 15.317, 'weight': 0, 'content': [{'end': 24.901, 'text': 'Just to cut to the chase, Big O notation is a way to measure how well a computer algorithm scales as the amount of data involved increases.', 'start': 15.317, 'duration': 9.584}, {'end': 32.764, 'text': 'So how well would it work in, say, if it was using a 10 element array versus a 10,000 element array?', 'start': 25.221, 'duration': 7.543}, {'end': 40.207, 'text': "As you're going to see here in a second, it's not always a measure of speed, but instead a measure of how well an algorithm scales.", 'start': 33.004, 'duration': 7.203}, {'end': 42.768, 'text': 'And this is going to be a rough overview of Big O,', 'start': 40.487, 'duration': 2.281}, {'end': 48.831, 'text': "and I'm not going to cover topics such as asymptotic analysis and other things that have to do with discrete mathematics.", 'start': 42.768, 'duration': 6.063}, {'end': 52.232, 'text': "I'm going to instead focus on the simple idea.", 'start': 49.051, 'duration': 3.181}, {'end': 53.833, 'text': "So I got a lot to do, so let's get into it.", 'start': 52.392, 'duration': 1.441}, {'end': 57.875, 'text': "Okay, so I'm doing a lot of this out of my head here, so bear with me.", 'start': 54.873, 'duration': 3.002}], 'summary': 'Big o notation measures algorithm scaling with data.', 'duration': 42.558, 'max_score': 15.317, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU15317.jpg'}], 'start': 0.129, 'title': 'Understanding big o notation', 'summary': 'Explains how big o notation measures the scalability of computer algorithms as the amount of data increases, focusing on the simple idea and not covering topics such as asymptotic analysis, providing a rough overview of big o.', 'chapters': [{'end': 57.875, 'start': 0.129, 'title': 'Understanding big o notation', 'summary': 'Explains how big o notation measures the scalability of computer algorithms as the amount of data increases, focusing on the simple idea and not covering topics such as asymptotic analysis, providing a rough overview of big o.', 'duration': 57.746, 'highlights': ['The chapter provides a simple explanation of how Big O notation measures the scalability of computer algorithms, focusing on how well an algorithm scales as the amount of data involved increases.', 'It emphasizes that Big O notation is not always a measure of speed, but rather a measure of scalability, exemplifying the comparison between using a 10 element array versus a 10,000 element array.', 'The tutorial aims to give a rough overview of Big O, excluding topics such as asymptotic analysis and discrete mathematics, and instead focusing on the fundamental concept.']}], 'duration': 57.746, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU129.jpg', 'highlights': ['The chapter provides a simple explanation of how Big O notation measures the scalability of computer algorithms, focusing on how well an algorithm scales as the amount of data involved increases.', 'It emphasizes that Big O notation is not always a measure of speed, but rather a measure of scalability, exemplifying the comparison between using a 10 element array versus a 10,000 element array.', 'The tutorial aims to give a rough overview of Big O, excluding topics such as asymptotic analysis and discrete mathematics, and instead focusing on the fundamental concept.']}, {'end': 219.89, 'segs': [{'end': 94.575, 'src': 'embed', 'start': 74.562, 'weight': 0, 'content': [{'end': 85.789, 'text': 'and the reason why this is going to be very important is I want to define with big O notation the part of the algorithm that has the greatest effect ultimately on the final answer.', 'start': 74.562, 'duration': 11.227}, {'end': 94.575, 'text': 'So now in this situation if n just goes up to being equal to 2, you could see very quickly that your answer is going to go from 84 to 459.', 'start': 85.929, 'duration': 8.646}], 'summary': 'Using big o notation to analyze algorithm, n=2 leads to answer increase from 84 to 459.', 'duration': 20.013, 'max_score': 74.562, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU74562.jpg'}, {'end': 158.617, 'src': 'embed', 'start': 119.269, 'weight': 2, 'content': [{'end': 125.952, 'text': "Which, as you can see, now you're starting to question, well definitely 19 doesn't really have that much bearing in regards to the final answer.", 'start': 119.269, 'duration': 6.683}, {'end': 133.037, 'text': 'And also when you think about it, n squared has very little to do with this answer, if, in fact,', 'start': 126.193, 'duration': 6.844}, {'end': 137.14, 'text': '45n cubed is going to be equal to 45,000 in this situation.', 'start': 133.037, 'duration': 4.103}, {'end': 140.023, 'text': "So, if you're going to be dealing with very, very large numbers,", 'start': 137.341, 'duration': 2.682}, {'end': 149.29, 'text': 'you very quickly see that the part of this algorithm that really has a lot to do with the final answer, as this data set scales,', 'start': 140.023, 'duration': 9.267}, {'end': 153.893, 'text': "is not even going to be the 45, but it's going to be the n cubed.", 'start': 149.29, 'duration': 4.603}, {'end': 158.617, 'text': 'And hence, we would say that this has an order of n cubed.', 'start': 154.174, 'duration': 4.443}], 'summary': 'Algorithm has an order of n cubed, with 45n cubed equal to 45,000.', 'duration': 39.348, 'max_score': 119.269, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU119269.jpg'}, {'end': 202.935, 'src': 'embed', 'start': 179.103, 'weight': 4, 'content': [{'end': 185.625, 'text': 'Order of n squared provide examples what that code looks like as well as n cubed and all these other ones.', 'start': 179.103, 'duration': 6.522}, {'end': 192.429, 'text': 'Also going to get into log n and order of n log n.', 'start': 185.985, 'duration': 6.444}, {'end': 194.83, 'text': "Okay, so that's what's going to be covered in this tutorial.", 'start': 192.429, 'duration': 2.401}, {'end': 199.113, 'text': "So I got to get a couple pieces here because we're going to be playing around with big giant arrays.", 'start': 194.97, 'duration': 4.143}, {'end': 202.935, 'text': "So I'm just going to create myself an integer array, call it the array.", 'start': 199.253, 'duration': 3.682}], 'summary': 'Tutorial covers examples of n squared, n cubed, log n, and n log n in code.', 'duration': 23.832, 'max_score': 179.103, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU179103.jpg'}], 'start': 58.035, 'title': 'Big o notation basics', 'summary': 'Explains the concept of big o notation using a simple algorithm (45n^3 + 20n^2 + 19), ultimately revealing the order of n^3. it also introduces the coverage of order of 1, order of n, order of n squared, n cubed, log n, and order of n log n in the tutorial.', 'chapters': [{'end': 219.89, 'start': 58.035, 'title': 'Big o notation basics', 'summary': 'Explains the concept of big o notation by using a simple algorithm (45n^3 + 20n^2 + 19) and demonstrates how the part of the algorithm with the greatest effect on the final answer is determined as n scales, ultimately revealing the order of n^3. it also introduces the coverage of order of 1, order of n, order of n squared, n cubed, log n, and order of n log n in the tutorial.', 'duration': 161.855, 'highlights': ['The algorithm (45n^3 + 20n^2 + 19) is used to demonstrate the concept of Big O notation, where the part of the algorithm with the greatest effect on the final answer is determined as n scales. 45n^3 + 20n^2 + 19', "As n increases from 1 to 2, the final answer jumps from 84 to 459, indicating the impact of scaling n on the algorithm's performance. 1 to 2, 84 to 459", 'With n increasing to 10, the final answer rises to 47 and 19, demonstrating the diminishing effect of the constant term and the lesser influence of n^2 on the final answer as compared to n^3. n increasing to 10, 47 and 19', "The scalability of the dataset reveals that as the numbers become very large, the part of the algorithm with the most impact on the final answer is n^3, leading to the determination of the algorithm's order as n^3. scenarios with very large numbers, n^3", 'Introduction and coverage of order of 1, order of n, order of n squared, n cubed, log n, and order of n log n are set to be covered in the tutorial. order of 1, order of n, order of n squared, n cubed, log n, order of n log n']}], 'duration': 161.855, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU58035.jpg', 'highlights': ['The algorithm (45n^3 + 20n^2 + 19) demonstrates Big O notation, determining the part with the greatest effect as n scales.', 'As n increases from 1 to 2, the final answer jumps from 84 to 459, indicating the impact of scaling n on performance.', 'With n increasing to 10, the final answer rises to 47 and 19, demonstrating the diminishing effect of the constant term and the lesser influence of n^2 compared to n^3.', "The scalability of the dataset reveals n^3 as the part with the most impact on the final answer, determining the algorithm's order as n^3.", 'Introduction and coverage of order of 1, order of n, order of n squared, n cubed, log n, and order of n log n are set to be covered in the tutorial.']}, {'end': 377.868, 'segs': [{'end': 273.745, 'src': 'embed', 'start': 242.797, 'weight': 2, 'content': [{'end': 245.098, 'text': "And I'm going to put this in here as a comment.", 'start': 242.797, 'duration': 2.301}, {'end': 252.26, 'text': "And what this algorithm does, or what this notation means, is it's going to be an algorithm that's going to execute in the same amount of time,", 'start': 245.218, 'duration': 7.042}, {'end': 254.281, 'text': 'regardless of the amount of data.', 'start': 252.26, 'duration': 2.021}, {'end': 260.702, 'text': "Or to put it another word, it's going to be code that executes in the same amount of time no matter how big the array is.", 'start': 254.501, 'duration': 6.201}, {'end': 262.683, 'text': 'So what exactly would that look like?', 'start': 261.043, 'duration': 1.64}, {'end': 273.745, 'text': 'Well, one example of that in the context of working with arrays would be if we wanted to add an item to an array and an integer was passed over and we said okay,', 'start': 262.883, 'duration': 10.862}], 'summary': 'Algorithm ensures constant execution time regardless of data size.', 'duration': 30.948, 'max_score': 242.797, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU242797.jpg'}, {'end': 351.582, 'src': 'embed', 'start': 324.822, 'weight': 0, 'content': [{'end': 331.046, 'text': 'And in the situation in which we just wanted to find one match, Big O notation is the same,', 'start': 324.822, 'duration': 6.224}, {'end': 337.011, 'text': "because what it's going to do is describe the worst case scenario, in which the whole array must be searched.", 'start': 331.046, 'duration': 5.965}, {'end': 341.874, 'text': "So let's say we're looking for an item that's in a 100,000 item array and it doesn't exist.", 'start': 337.251, 'duration': 4.623}, {'end': 347.338, 'text': 'but we want to make sure that we handle that example, which would mean that every single item would have to be searched.', 'start': 341.874, 'duration': 5.464}, {'end': 351.582, 'text': "So let's just come in here and let's do this with linear search.", 'start': 347.698, 'duration': 3.884}], 'summary': 'Big o notation describes worst case scenario, like searching a 100,000 item array with linear search.', 'duration': 26.76, 'max_score': 324.822, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU324822.jpg'}], 'start': 219.89, 'title': 'Big o notation explained', 'summary': 'Explains o(1) and o(n) notations using code examples to demonstrate algorithms executing in constant time and growing in direct proportion to data size, with provided code available in the video link.', 'chapters': [{'end': 377.868, 'start': 219.89, 'title': 'Big o notation explained', 'summary': 'Explains the concepts of o(1) and o(n) notations using code examples to demonstrate algorithms that execute in constant time and grow in direct proportion to the data size, with the provided code available in the video link.', 'duration': 157.978, 'highlights': ['The concept of O(1) notation is explained using an example of adding an item to an array, showcasing code that executes in the same amount of time regardless of the array size. example of adding an item to an array', 'The chapter delves into the concept of O(n) notation by demonstrating a linear search algorithm, highlighting how its time to complete grows in direct proportion to the amount of data. demonstrating a linear search algorithm', "The worst-case scenario is described using Big O notation, emphasizing the need to search the entire array when looking for an item, even in a 100,000 item array where the item doesn't exist. searching the entire array in a worst-case scenario"]}], 'duration': 157.978, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU219890.jpg', 'highlights': ["The worst-case scenario is described using Big O notation, emphasizing the need to search the entire array when looking for an item, even in a 100,000 item array where the item doesn't exist.", 'The chapter delves into the concept of O(n) notation by demonstrating a linear search algorithm, highlighting how its time to complete grows in direct proportion to the amount of data.', 'The concept of O(1) notation is explained using an example of adding an item to an array, showcasing code that executes in the same amount of time regardless of the array size.']}, {'end': 849.915, 'segs': [{'end': 450.228, 'src': 'embed', 'start': 418.614, 'weight': 0, 'content': [{'end': 422.976, 'text': 'and then if we wanted to say print something out on the screen, we could say something like value,', 'start': 418.614, 'duration': 4.362}, {'end': 430.039, 'text': 'found value in array and then throw end time into this to calculate whenever this guy ended execution.', 'start': 422.976, 'duration': 7.063}, {'end': 434.461, 'text': 'And then we could say something like linear search took end time, minus start time.', 'start': 430.339, 'duration': 4.122}, {'end': 439.023, 'text': "And then let's bounce back up into the main function here and do some tests.", 'start': 434.661, 'duration': 4.362}, {'end': 442.064, 'text': 'So we go to notation, test algo.', 'start': 439.363, 'duration': 2.701}, {'end': 450.228, 'text': "I'm going to just say 2, big O notation, and let's say I set this for, I'm going to set it for 100,000 as the size of my array.", 'start': 442.483, 'duration': 7.745}], 'summary': 'The transcript discusses implementing algorithms and testing them, with an example of setting the array size to 100,000.', 'duration': 31.614, 'max_score': 418.614, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU418614.jpg'}, {'end': 492.588, 'src': 'embed', 'start': 462.077, 'weight': 2, 'content': [{'end': 465.179, 'text': "but I didn't do it for the constructor, which isn't a big deal.", 'start': 462.077, 'duration': 3.102}, {'end': 467.8, 'text': "I'm just going to say int size of the array.", 'start': 465.299, 'duration': 2.501}, {'end': 470.26, 'text': 'Array size is going to be whatever was passed into it.', 'start': 467.82, 'duration': 2.44}, {'end': 471.041, 'text': 'And there we are.', 'start': 470.46, 'duration': 0.581}, {'end': 472.281, 'text': 'We just created our new array.', 'start': 471.081, 'duration': 1.2}, {'end': 478.663, 'text': "Go back up into main and let's create a couple more of these arrays so that we can compare them based off of size differences.", 'start': 472.481, 'duration': 6.182}, {'end': 480.523, 'text': 'So test algo 3.', 'start': 478.723, 'duration': 1.8}, {'end': 481.864, 'text': "And let's change this to 200,000.", 'start': 480.523, 'duration': 1.341}, {'end': 485.845, 'text': "And let's create two more of them just to experiment with.", 'start': 481.864, 'duration': 3.981}, {'end': 487.365, 'text': 'And change this to 4.', 'start': 486.005, 'duration': 1.36}, {'end': 492.588, 'text': 'this to 5, change this to 4, 5, and have this be 3, and this be 400,000.', 'start': 487.365, 'duration': 5.223}], 'summary': 'Creating and comparing arrays of different sizes for experimentation.', 'duration': 30.511, 'max_score': 462.077, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU462077.jpg'}, {'end': 542.086, 'src': 'heatmap', 'start': 499.432, 'weight': 1, 'content': [{'end': 506.396, 'text': "in essence, is going to be to show that they're going to scale, as the number of elements that we're going to be using here are going to scale.", 'start': 499.432, 'duration': 6.964}, {'end': 508.076, 'text': 'which makes 100% sense.', 'start': 506.656, 'duration': 1.42}, {'end': 510.697, 'text': "Actually, I don't even think I need to use all those.", 'start': 508.577, 'duration': 2.12}, {'end': 512.758, 'text': "And let's file save as long as I did it right.", 'start': 510.977, 'duration': 1.781}, {'end': 520.28, 'text': 'And you can see right there with this linear search, this took roughly 4 milliseconds, this took 5 milliseconds, and this took 18 milliseconds.', 'start': 512.938, 'duration': 7.342}, {'end': 525.361, 'text': 'So you can see, as the number of elements scale get bigger the number of elements we have to deal with.', 'start': 520.52, 'duration': 4.841}, {'end': 527.982, 'text': 'that is in direct relation to the number of elements.', 'start': 525.361, 'duration': 2.621}, {'end': 531.582, 'text': 'And that is why it is known as order of n.', 'start': 528.382, 'duration': 3.2}, {'end': 533.283, 'text': "So there's an example of order of n.", 'start': 531.582, 'duration': 1.701}, {'end': 542.086, 'text': "So now let's take a look at what does order of n squared mean or cubed or any of these other different things we could put inside of here.", 'start': 534.542, 'duration': 7.544}], 'summary': 'Demonstrating scaling with linear search, 4ms-18ms, and order of n.', 'duration': 33.851, 'max_score': 499.432, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU499432.jpg'}, {'end': 722.005, 'src': 'heatmap', 'start': 672.731, 'weight': 4, 'content': [{'end': 677.517, 'text': 'And there you can see it took 362 milliseconds and it took 1612 milliseconds.', 'start': 672.731, 'duration': 4.786}, {'end': 679.899, 'text': 'And you can see that it just continues going on here.', 'start': 677.837, 'duration': 2.062}, {'end': 686.347, 'text': 'And how dramatically slower the bubble sort gets depending upon the amount of data.', 'start': 680.12, 'duration': 6.227}, {'end': 690.992, 'text': 'And that is why order of n squared is very bad and to be avoided.', 'start': 686.547, 'duration': 4.445}, {'end': 697.674, 'text': "So now let's show you an example of another algorithm that is much more efficient, and that's going to be our binary search.", 'start': 691.332, 'duration': 6.342}, {'end': 703.315, 'text': "And here we're going to focus on order of log n as our big O notation.", 'start': 698.094, 'duration': 5.221}, {'end': 709.957, 'text': 'And this is going to occur when data being used is decreased roughly by 50% each time through the algorithm.', 'start': 703.535, 'duration': 6.422}, {'end': 713.338, 'text': 'And the binary search, like we saw before, is a perfect example of this.', 'start': 710.117, 'duration': 3.221}, {'end': 722.005, 'text': "And it's pretty fast, because as log n increases, or n specifically increases,", 'start': 713.778, 'duration': 8.227}], 'summary': 'Bubble sort is slow, with o(n^2), while binary search is efficient with o(log n).', 'duration': 40.607, 'max_score': 672.731, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU672731.jpg'}], 'start': 378.048, 'title': 'Understanding big o notation and algorithm performance', 'summary': "Discusses the implementation of linear search algorithm and the testing of its execution time with varying array sizes, demonstrating the scaling impact on performance. it also explains the concepts of 'order of n', 'order of n squared', and 'order of log n' using examples such as linear search, bubble sort, and binary search, highlighting their time complexity and efficiency.", 'chapters': [{'end': 512.758, 'start': 378.048, 'title': 'Understanding big o notation and algorithm performance', 'summary': 'Discusses the implementation of linear search algorithm and the testing of its execution time with varying array sizes, demonstrating the scaling impact on performance.', 'duration': 134.71, 'highlights': ['The chapter discusses the implementation of linear search algorithm and the testing of its execution time with varying array sizes The transcript describes the process of implementing a linear search algorithm and conducting tests with arrays of different sizes to evaluate the impact on performance.', 'The chapter emphasizes the scaling impact on performance as the number of elements in the array increases It is highlighted that the linear searches demonstrate scaling impact, showing that the performance scales with the number of elements in the array.', 'The testing involves varying array sizes, including 100,000, 200,000, and 400,000 elements The chapter includes tests with array sizes of 100,000, 200,000, and 400,000, demonstrating the impact of different array sizes on the performance of the linear search algorithm.']}, {'end': 849.915, 'start': 512.938, 'title': 'Big o notations explained', 'summary': "Explains the concepts of 'order of n', 'order of n squared', and 'order of log n' using examples such as linear search, bubble sort, and binary search, highlighting their time complexity and efficiency.", 'duration': 336.977, 'highlights': ['The linear search took roughly 18 milliseconds as the number of elements increased, demonstrating the order of n complexity. Linear search demonstrated the order of n complexity, with the time taken increasing as the number of elements scaled up.', "The bubble sort took 1612 milliseconds for 20,000 items, illustrating the dramatic decrease in performance with the increase in the number of items, representing the order of n squared complexity. Bubble sort's time complexity was demonstrated as order of n squared with a dramatic decrease in performance as the number of items increased, taking 1612 milliseconds for 20,000 items.", 'The binary search, with order of log n complexity, showed little or no effect in speed even with a dramatic increase in the data set, due to the halving of data at each iteration. Binary search, with order of log n complexity, exhibited little or no effect in speed even with a dramatic increase in the data set, attributed to the halving of data at each iteration.']}], 'duration': 471.867, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU378048.jpg', 'highlights': ['The chapter discusses the implementation of linear search algorithm and the testing of its execution time with varying array sizes', 'The chapter emphasizes the scaling impact on performance as the number of elements in the array increases', 'The testing involves varying array sizes, including 100,000, 200,000, and 400,000 elements', 'The linear search took roughly 18 milliseconds as the number of elements increased, demonstrating the order of n complexity', 'The bubble sort took 1612 milliseconds for 20,000 items, illustrating the dramatic decrease in performance with the increase in the number of items, representing the order of n squared complexity', 'The binary search, with order of log n complexity, showed little or no effect in speed even with a dramatic increase in the data set, due to the halving of data at each iteration']}, {'end': 1229.631, 'segs': [{'end': 913.911, 'src': 'embed', 'start': 876.531, 'weight': 1, 'content': [{'end': 890.634, 'text': "This took 721 milliseconds and now you can start to see why measuring the time doesn't really matter with efficient algorithms and why big O notation tells you a lot more about an algorithm than how long or milliseconds it would take to execute.", 'start': 876.531, 'duration': 14.103}, {'end': 892.655, 'text': 'And you can also see the efficiency.', 'start': 890.854, 'duration': 1.801}, {'end': 900.461, 'text': 'it only went through it nine times to search 10,000 items and it only went through it 10 times to search through 20,000 items.', 'start': 892.655, 'duration': 7.806}, {'end': 903.503, 'text': 'So this is pretty much the picture of efficiency.', 'start': 900.761, 'duration': 2.742}, {'end': 910.649, 'text': 'And I executed again, just so you could see that that was meant to be binary search took zero, not bubble sort, say binary search took zero.', 'start': 903.644, 'duration': 7.005}, {'end': 912.67, 'text': 'So that is the picture of efficiency.', 'start': 910.829, 'duration': 1.841}, {'end': 913.911, 'text': 'And I hope that makes sense.', 'start': 912.95, 'duration': 0.961}], 'summary': 'Efficient algorithm took 721 milliseconds, went through 10,000 items 9 times, and through 20,000 items 10 times, demonstrating the effectiveness of big o notation.', 'duration': 37.38, 'max_score': 876.531, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU876531.jpg'}, {'end': 992.056, 'src': 'heatmap', 'start': 955.255, 'weight': 3, 'content': [{'end': 958.176, 'text': 'And we already know that the quick sort is much more efficient.', 'start': 955.255, 'duration': 2.921}, {'end': 961.137, 'text': 'But the main answer is going to be why is it so efficient??', 'start': 958.276, 'duration': 2.861}, {'end': 965.999, 'text': 'Now, to figure out the number of comparisons that we need to make with the quicksort,', 'start': 961.297, 'duration': 4.702}, {'end': 972.141, 'text': 'we first need to remember that it is comparing and moving values very efficiently, without shifting,', 'start': 965.999, 'duration': 6.142}, {'end': 975.303, 'text': "unlike some of the other sorting algorithms we've used in the past.", 'start': 972.141, 'duration': 3.162}, {'end': 979.805, 'text': 'And that means that values are only going to be compared once.', 'start': 975.523, 'duration': 4.282}, {'end': 983.208, 'text': "They're not going to be compared to each other over and over and over again.", 'start': 980.145, 'duration': 3.063}, {'end': 989.514, 'text': 'So in essence, each comparison will reduce the possible final sorted lists in half.', 'start': 983.428, 'duration': 6.086}, {'end': 992.056, 'text': 'Or to put it in a completely other way,', 'start': 989.854, 'duration': 2.202}], 'summary': 'Quick sort is efficient due to minimal value comparisons and reduced final sorted lists by half.', 'duration': 36.801, 'max_score': 955.255, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU955255.jpg'}, {'end': 1218.038, 'src': 'embed', 'start': 1187.357, 'weight': 0, 'content': [{'end': 1189.238, 'text': 'Throw in these timing mechanisms here.', 'start': 1187.357, 'duration': 1.881}, {'end': 1193.4, 'text': "Just to show you how efficient it is, I'm going to chuck this up to 100,000 and chuck this up to 200,000.", 'start': 1189.538, 'duration': 3.862}, {'end': 1196.982, 'text': "Test I'll go to here.", 'start': 1193.4, 'duration': 3.582}, {'end': 1198.303, 'text': "We're gonna do the quicksort.", 'start': 1197.202, 'duration': 1.101}, {'end': 1199.344, 'text': 'Where is that quicksort?', 'start': 1198.483, 'duration': 0.861}, {'end': 1202.386, 'text': 'There it is set into zero test.', 'start': 1200.064, 'duration': 2.322}, {'end': 1210.773, 'text': "I'll go to pass in the number of items in the array and execute and you could see it cycled through a hundred thousand items in 41 milliseconds.", 'start': 1202.386, 'duration': 8.387}, {'end': 1214.936, 'text': "Let's take this up to four, just by changing this to four, I'll say, of execute,", 'start': 1210.773, 'duration': 4.163}, {'end': 1218.038, 'text': 'and only took 44 milliseconds to jump up to 400,000 or 300,000 in this situation.', 'start': 1214.936, 'duration': 3.102}], 'summary': 'Efficient quicksort algorithm processed 100,000 items in 41 ms, 400,000 in 44 ms.', 'duration': 30.681, 'max_score': 1187.357, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU1187357.jpg'}], 'start': 850.136, 'title': 'Efficiency of binary search and big o notation', 'summary': 'Discusses the efficiency of binary search, demonstrating its speed in searching 10,000 and 20,000 items, alongside explaining the efficiency of quicksort with a quicksort implementation handling 100,000 items in 41 milliseconds.', 'chapters': [{'end': 913.911, 'start': 850.136, 'title': 'Efficiency of binary search', 'summary': 'Discusses the efficiency of binary search, highlighting that it took 721 milliseconds to search 10,000 items and 162 milliseconds to search 20,000 items, showcasing the significant improvement in efficiency and the effectiveness of big o notation in understanding algorithm efficiency.', 'duration': 63.775, 'highlights': ['Binary search took 721 milliseconds to search 10,000 items and 162 milliseconds to search 20,000 items, demonstrating a significant improvement in efficiency.', 'Big O notation provides more insights into algorithm efficiency than measuring time in milliseconds, indicating the importance of understanding algorithm complexity.', 'The search only went through it nine times to search 10,000 items and 10 times to search through 20,000 items, emphasizing the efficiency of the binary search algorithm.']}, {'end': 1229.631, 'start': 914.191, 'title': 'Understanding big o notation', 'summary': 'Explains the efficiency of quicksort, highlighting that its number of comparisons is n log n, unlike inefficient sorting algorithms like bubble sort, and demonstrates its efficiency through a quicksort implementation handling 100,000 items in 41 milliseconds.', 'duration': 315.44, 'highlights': ['The number of comparisons in quicksort is n log n, making it more efficient than bubble sort with n squared comparisons.', 'A demonstration showed quicksort handling 100,000 items in 41 milliseconds, showcasing its efficiency.', 'The explanation of the quicksort algorithm and its partitioning process provides insights into its efficiency and effectiveness.']}], 'duration': 379.495, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/V6mKVRU1evU/pics/V6mKVRU1evU850136.jpg', 'highlights': ['Quicksort handled 100,000 items in 41 milliseconds, demonstrating its efficiency.', 'Binary search took 721 milliseconds to search 10,000 items and 162 milliseconds to search 20,000 items, showing significant improvement in efficiency.', 'Big O notation provides more insights into algorithm efficiency than measuring time in milliseconds, indicating the importance of understanding algorithm complexity.', 'The number of comparisons in quicksort is n log n, making it more efficient than bubble sort with n squared comparisons.', 'The search only went through it nine times to search 10,000 items and 10 times to search through 20,000 items, emphasizing the efficiency of the binary search algorithm.', 'The explanation of the quicksort algorithm and its partitioning process provides insights into its efficiency and effectiveness.']}], 'highlights': ['The tutorial aims to give a rough overview of Big O, excluding topics such as asymptotic analysis and discrete mathematics, and instead focusing on the fundamental concept.', 'The algorithm (45n^3 + 20n^2 + 19) demonstrates Big O notation, determining the part with the greatest effect as n scales.', "The scalability of the dataset reveals n^3 as the part with the most impact on the final answer, determining the algorithm's order as n^3.", "The worst-case scenario is described using Big O notation, emphasizing the need to search the entire array when looking for an item, even in a 100,000 item array where the item doesn't exist.", 'The concept of O(1) notation is explained using an example of adding an item to an array, showcasing code that executes in the same amount of time regardless of the array size.', 'The linear search took roughly 18 milliseconds as the number of elements increased, demonstrating the order of n complexity.', 'The bubble sort took 1612 milliseconds for 20,000 items, illustrating the dramatic decrease in performance with the increase in the number of items, representing the order of n squared complexity.', 'The binary search, with order of log n complexity, showed little or no effect in speed even with a dramatic increase in the data set, due to the halving of data at each iteration.', 'Quicksort handled 100,000 items in 41 milliseconds, demonstrating its efficiency.', 'Binary search took 721 milliseconds to search 10,000 items and 162 milliseconds to search 20,000 items, showing significant improvement in efficiency.', 'Big O notation provides more insights into algorithm efficiency than measuring time in milliseconds, indicating the importance of understanding algorithm complexity.', 'The number of comparisons in quicksort is n log n, making it more efficient than bubble sort with n squared comparisons.', 'The search only went through it nine times to search 10,000 items and 10 times to search through 20,000 items, emphasizing the efficiency of the binary search algorithm.', 'The explanation of the quicksort algorithm and its partitioning process provides insights into its efficiency and effectiveness.']}