Complexity Analysis

Explore how to analyze the time complexity of the Sieve of Eratosthenes algorithm. Understand the behavior of nested loops dependent on prime numbers and grasp why the overall complexity is O(N log log N). This lesson prepares you to optimize implementations for competitive programming contests.

We'll cover the following...

The outer loop

for (int i = 2; i * i <= N; i++)

Runs for $\sqrt{N}$ values but the number of iterations of the inner loop is dependent on $i$ .

for (int j = i + i; j <= N; j += i)

Also, note that the inner loop only runs for values when $i$ is prime.

$i$	Inner loop iterations
2	$\frac{N}{2}$
3	$\frac{N}{3}$

...

1.Introduction

2.Complexity Analysis

3.Number Theory

4.Arrays and Vectors

5.Sieve of Eratosthenes

6.Strings

7.Sorting

8.Linked List

9.Stack

10.Queue

11.Binary Tree

12.2 Pointers

13.Heap

14.Binary Search Tree

15.Balanced Binary Search Tree

16.Course Conclusion

Complexity Analysis