Time complexity of Sieve of Eratosthenes algorithm

by

  1. Your n/2 + n/3 + n/5 + … n/97 is not O(n), because the number of terms is not constant. [Edit after your edit: O(n2) is too loose an upper bound.] A loose upper-bound is n(1+1/2+1/3+1/4+1/5+1/6+…1/n) (sum of reciprocals of all numbers up to n), which is O(n log n): see Harmonic number. A more proper upper-bound is n(1/2 + 1/3 + 1/5 + 1/7 + …), that is sum of reciprocals of primes up to n, which is O(n log log n). (See here or here.)

  2. The “find the next prime number” bit is only O(n) overall, amortized — you will move ahead to find the next number only n times in total, not per step. So this whole part of the algorithm takes only O(n).

So using these two you get an upper bound of O(n log log n) + O(n) = O(n log log n) arithmetic operations. If you count bit operations, since you’re dealing with numbers up to n, they have about log n bits, which is where the factor of log n comes in, giving O(n log n log log n) bit operations.

More Related Contents:

  1. Showing the order of growth of the function
  2. What is a plain English explanation of “Big O” notation?
  3. Big O, how do you calculate/approximate it?
  4. How can I find the time complexity of an algorithm?
  5. What does O(log n) mean exactly?
  6. Segmented Sieve of Eratosthenes?
  7. Can hash tables really be O(1)?
  8. Difference between Big-O and Little-O Notation
  9. Is there an O(n) integer sorting algorithm?
  10. Hash table runtime complexity (insert, search and delete)
  11. What is an Efficient algorithm to find Area of Overlapping Rectangles
  12. Time complexity of Euclid’s Algorithm
  13. What would cause an algorithm to have O(log log n) complexity?
  14. What is pseudopolynomial time? How does it differ from polynomial time?
  15. how to calculate binary search complexity
  16. What would cause an algorithm to have O(log n) complexity?
  17. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  18. Fast algorithm implementation to sort very small list
  19. Argument for O(1) average-case complexity of heap insertion
  20. Sorting in linear time? [closed]
  21. Efficient maths algorithm to calculate intersections
  22. Why is the time complexity of both DFS and BFS O( V + E )
  23. O(klogk) time algorithm to find kth smallest element from a binary heap
  24. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  25. Optimizing Conway’s ‘Game of Life’
  26. Move all odd positioned element to left half and even positioned to right half in-place
  27. Can an array be grouped more efficiently than sorted?
  28. How do I find the median of numbers in linear time using heaps?
  29. Computational complexity of base conversion
  30. Merge sort time and space complexity

Leave a Comment