Time Complexity Explained | Why You Should Optimize Code
In the first case:
Time Complexity: O(n) In the worst case (when n is prime), the loop iterates n-2 times. This makes the time complexity linear, or O(n).
In the second case:
Time Complexity: O(sqrt(n)) The key optimization is that we only need to check for divisors up to the square root of n. If a number n has a divisor larger than sqrt(n), it must also have a divisor smaller than sqrt(n). This significantly reduces the number of iterations. The further optimization of checking numbers of the form 6k ± 1 reduces the number of checks even further.
As you can see, the optimized method is significantly faster, especially for the larger number. This demonstrates the practical impact of reducing time complexity from O(n) to O(sqrt(n)). The larger the input (n), the more pronounced this difference will be.
Key takeaway: By understanding and optimizing algorithms, you can drastically improve the performance of your programs, especially when dealing with large datasets or computationally intensive tasks. The change from checking every number up to n to checking up to the square root of n is a very common and effective optimization.
GitHub Repo
github.com/sanjibsinha/MyFirstPythonProject/blob/master/basic_vs_optimized.py
Watch video Time Complexity Explained | Why You Should Optimize Code online without registration, duration hours minute second in high quality. This video was added by user AICodeSchool 25 December 2024, don't forget to share it with your friends and acquaintances, it has been viewed on our site 4 once and liked it 0 people.