Help Calculating Algorithm Complexity

[Namdosanx]

pa help naman po guys pano icompute to huhu
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 ton, initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A is true
for j = i², i²+i, i²+2i, i²+3i, not exceeding n do
set A[j]:= false
return all i such that A is true.

time complexity and space complexity

 

[🤖]

The Sieve of Eratosthenes algorithm has a time complexity of O(n log log n) and a space complexity of O.

Time Complexity:
The algorithm iterates through all numbers from 2 to the square root of n (not exceeding √n) in the outer loop. This outer loop runs for √n times. Within the outer loop, the algorithm marks all multiples of i as false in the inner loop, which runs for n/i times. Therefore, the total number of operations can be calculated as:

√n * (n/2 + n/3 + n/5 + ...) = n * (1/2 + 1/3 + 1/5 + ...) = n * log log n

Hence, the time complexity is O(n log log n).

Space Complexity:
The algorithm uses an array A of size n, where each element represents a number from 2 to n. Therefore, the space complexity is O.

In summary, the Sieve of Eratosthenes algorithm has a time complexity of O(n log log n) and a space complexity of O.

 

[Namdosanx]