Sieve Of Eratosthenes | Mathematics | Data Structures and Algorithm | Python

Problem Statement:

The Sieve of Eratosthenes is a method for finding all primes up to (and possibly including) a given natural n$n\text{.}$ This method works well when n$n$ is relatively small, allowing us to determine whether any natural number less than or equal to $n$ is prime or composite.

Explanation:

Suppose n = 100

Step 1: A/c to the algorithm we will mark all the numbers which are divisible by 2 and are greater than or equal to the square of it.

Step 2: Now move to next unmarked number 3 and mark all the numbers which are multiple of 3 and are greater than the square of it.

Now move to next unmarked number 5 and mark all the numbers which are multiple of 5 and are greater than the square of it.

Now move to next unmarked number 5 and mark all the numbers which are multiple of 5 and are greater than the square of it.

Now we have reached the limit. All the unmarked numbers are prime numbers.

So the list of prime numbers are:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Code: 

See you in the next article.

Until Then...

Byeeee

Use Class to Store Name and Marks of Students and Store them in List | OOP | Classes and Object

Problem Statement: 

            

        Write a program that uses a class to store the names and marks of students. Use the list to store the marks in three subjects...

Example:

Input:

Enter the marks of Joey in subject 1: 89
Enter the marks of Joey in subject 2: 88
Enter the marks of Joey in subject 3: 87
Enter the marks of Monica in subject 1: 78
Enter the marks of Monica in subject 2: 98
Enter the marks of Monica in subject 3: 99

Output:

Joey got [89, 88, 87]
Monica got [78, 98, 99]

Note: eat(); sleep(); code(); repeat(); requests you to try this out yourself first...

Python Code:

Comment down below if you have any doubt...

Subscribe to get notify when new article is uploaded.

Analysis of Recursive Function

 In the previous post, we have studied, Complexity Analysis of Common Loops, 

As you go through this, the journey of understanding Data Structures, to make your code more efficient you will use the concept of Recursion.

When we analyze these functions, we get a recurrence relation for time complexity. For example in Binary Search, to search a given element, we divide the array/list into two halves and recursively repeat the process for two halves, until we get the element we are searching for. The time complexity of Binary Search is T(n) = T(n/2) + c  i.e., Ө(log n). There are many such algorithms like Tower of Hanoi, Josephus Problem, and many more.

We have three methods, for calculating the Complexity of the Recursive Function.|
1) Substitution methods
2) Tracing Tree Methods
3) Master Theorem

First, let's take a simple example, 

void Test(int n) {                --- T(n)
    if (n < 0) {
        printf("%d", n);            --- 1
        Test(n-1);                --- T(n-1)
    }
}

So, we have time Complexity function T(n) = T(n-1)+1

Now, let's first discuss it by Tracing Tree Method...

        Test(3)                -- 1 unit of time
        /         \

print(3)      Test(2)            ---     1 unit of time

                    /      \
           print(2)      Test(1)        --- 1 unit of time
                            /       \

                 print(1)       Test(0)        --- 1 unit of time
                                        |

                                       X

Hence, f(n) = n+1
where n is the number of prints, 

Hence,

Time Complexity is: O(n)

Now let's analyze the same algorithm using the Substitution Method.

Let us suppose the time taken for this algorithm is T(n)

T(n) =  {1,             n = 0

            {T(n-1)+1, n > 0

So, let's consider,

        T(n) = T(n-1)+1

        Substitute T(n-1)   --------- as if

  T(n) = T(n-1)+1 then,

T(n-1) = T(n-2) +1

So, we have

T(n) = [T(n-2)+1] +1

T(n) = T(n-2) + 2
Simirally, T(n) = [T(n-3)+1] +2

T(n) = T(n-3) +3

            :

            :        continue for k times
            :

T(n) = T(n-k) + k

Let's assume n-k = 0

        ∴ n = k

So, we have:

        T(n) = T(n-n) + n

T(n) = T(0) + 1

but a/c to our algorithm if n = 0 then T(n) = 1 i.e., T(0) = 1

 ∴ T(n) = 1+n

And hence, 

Time Complexity is O(n)

Now, let's consider Master Theorem:

The master theorem is a formula for solving recurrence relations of the form:

T(n) = aT(n/b) + f(n)

here, 

n = size of output

a = number of subproducts

n/b = size of each subproblem.

        And all subproblems are assumed to have the same size.

f(n) = cost of the work done outside the recursive call.

            which include the cost of dividing the problem and 

            cost of merging the solutions.

Here, a ≥ 1 and b > 1 are constants and are an asymptotically positive function.

And Here, 

T(n) has the following asymptotic bounds:

    1) if f(n) = O(n^{log_b a-ο}), then T(n) =  Ө(n^log_b a).

    2) if f(n) = Ө(n^log_b a), then T(n) = Ө(n^log_b a * log n).

    3) if f(n) = Ω(n^log_b a+ο), then T(n) = Ө(f(n))

here,

ο > 0 is a constant

Each of the above conditions can be clarified as,

1. If the cost of solving the sub-problems at each level is increased by a certain factor, the value of f(n) will become polynomially smaller than n^log_b a. Thus the time complexity is oppressed by the cost of the last level i.e., n^log_b a.
2. If the cost of solving the sub-problem at each level is nearly equal, then the value of f(n) will be n^log_b a. Thus the time complexity will be f(n) times the total number of levels i.e., n^log_b a * log n.
3. If the cost of solving the sub-problems at each level decreases by a certain factor, the value of f(n) will become polynomially larger than n^log_b a. Thus, the time complexity is oppressed by the cost of f(n).

Note: Pretty Soon I will make a video explaining all these Recursive Analysis Methods with examples.

The link will be provided here ...

By this,

It's Harsh Jaiswal

Signing Of...

Complexity Analysis of common loops

 For analyzing, the time is taken or space allotted for the loops like for and while there is the method called frequency count method. Look for the algorithm below...

Example 1:

Algorithm Sum(A, n){
    s = 0;                                     --> 1 unit
    for (i=0; i < n; i++){                     --> n+1 unit
        s = s + A[i];                          --> n unit
    }
    return s;                                  --> 1 unit
}                                            Total=> 1+n+1+n+1 = 2n+3

The time taken by the algorithm can be known by assigning one unit of time for each statement and if any statement is repeating for some number of times. The frequency of that statement or frequency for executing that statement will be calculated and we get the time taken for the algorithm.

The for loop you have here has, n + 1 units because, the condition I < n is checked n + 1 time.  

And for space complexity:
    We have 4 variables A, n, s, and i. A is an array that can have n elements, hence going to take n space. Rest variables n, s, and i have fixed values so the space taken is 1 unit each. (so, we have n+3)

So, Here 
Time Complexity: 2n + 3    : O(n)
Space Complexity: n + 3    : O(n)

Example 2:

Algorithm Add(A, B, n){
    for (i=0; i < n; i++){                    --> n + 1

        for (j = 0; j < n; j++){                --> n(n+1)
            c[i,j] = A[i, j] + B[i, j]        --> n x n
        }
    }
}

Time Complexity: (n+1)+n(n+1)+n² = n² + 2n + 1 = O(n²)
Space Complexity: O(n²)

Example 3:

Algorithm Multiply(A, B, n){
    for (i = 0; i < n; i++){            --> n+1
        for (j = 0; j < n; j++){          --> n(n+1)
            c[i][j] = 0;                    --> nxn
            for (k = 0; k < n; k++){            --> n x n x n+1
                c[i, j] = c[i, j] + A[i, k] * B[k, j];      --> n x n x n
            }
        }
    }
}

Time Complexity: (n+1)+n(n+1)+n²+n²(n+1)+n³ = 2n³+3n²+2n+1 = O(n³)
Space Complexity: O(n²)

Example 4: 

for (i = 1;  i < n; i = i+2){
    sum++;                            --> n/2
}

Time Complexity: n/2 = O(n)

Example 5: 

for (i = 0; i < n; i++){             --> n+1
    for (j = 0; j < n; j++){            --> n(n+1)
        sum++;                    --> n(n)
    }
}

Time Complexity: n + 1 + n² + n + n² = 2n² + 2n + 1 = O(n²)

Example 6:

for (i = 0; i < n; i++){
    for (j = 0; j < i; j++){
        stmt;
    }
}

Time Complexity: 0 + 1 + 2 + 3 + ... + n = n(n+1)/2 = (n² + n)/2 = O(n²)

Example 7:

p = 0;
for (i = 0; p <= n; i++){
    p = p + i;
}

Assume: p > n (it will stop)

        ∵ p = k(k+1)/2

            k(k+1)/2 > n        (it will stop)

            k² > n

        ∴ k > √n

∴ it will execute for O(√n)

Example 8:

for (i = 1; i < n; i=i*2){
    sum ++;
}

Assume i >= n  (it will stop)

            i = 2^k

            2^k >= n

            2^k = n

                k = log₂n

Time Complexity: O(log₂ n)

Example 9: 

for (i = n; i > = 1; i = 1/2)
        stmt1;

Assume i < 1
            n/2^k < 1

   for simplicity above can be written as,
            n/2^k = 1

            n = 2^k
        log₂ n = k

Time Complexity: O(log₂ n)

Example 10:

for (i = 0; i*i < n; i++)
        stmt;

i*i >= n

i² = n

i = √n

Time Complexity: O(√n)

Try this out...

Q.11) 

for (i = 0; i < n; i++)
    stmt1;
for (j = 0; j < n; j++)
    stmt2;

Q.12)

p = 0
for (i = 1; i < n; i = i*2)
    p++;
for (j = 1; j < p; j = j*2)
    stmt;

Q.13)

for (i = 0; i < n; i++) {
    for (j = 1; j < n; j = j * 2) {
        stmt;
    }
}

For Summarizing.
We have,

for(i = 0; i < n; i++)        --- O(n)
for(i = 0; i < n; i = i+2)    --- O(n)
for(i = n; i>1; i--)            --- O(n)
for(i = 1; i < n; i=i*2)        --- O(log2 n)
for(i = 1; i < n; i=i*3)        --- O(log3 n)
for(i = n; i>1; i = i/2)        --- O(log2 n)

As we have for loop, similarly we have complexity analysis of while loop.

Example 14.

i = 0;                    -- 1
while (i<n){                -- n + 1
    stmt;                -- n
    i++;                  -- n
}                    
                     ====================
                        f(n) = 3n+1 = O(n)

Time Complexity: O(n)

Example 15:

i = 1;
k = 1;
while (k<n){
    stmt;
    k = k + 1;
    i++;
}

Analysis:

        Values of x        Values of k
                1                        1
                2                    1+1
                3                    1+1+2
                4                    1+1+2+3
                5                    1+1+3+4
                :                            :
                :                            :
                m                    1+2+3+4+...+m
So, we have

             k ≥ n
         m(m+1)/2 ≥ n
                m² ≥ n        (Approx.)
        ∴ f(n) = O(√n)
Time Complexity: O(√n)

Try this out...

Q. 16)

while (m!=n){
    if (m>n)
        m = m -n;
    else
        n = n-m;
}

Q.17)

Algorithm Test(n){
    if (n < 5)
        print "%d ", n;
    else {
        for ( i = 0; i < n; i++)
            print "%d ", i;
    }
}

So, By this I End this post, next we will be discussing, Analysis Of Recursion

It's Harsh Jaiswal
Signing of...

Thanks...

Asymptotic Notation - 22 Weeks of DSA

 In the previous post (Click to visit), we have already studied about Best, Average, and Worst-Case. 

Order of Growth: (It's very important)

c < log log n < log n < n^1/3 < n^1/2 < n < n² < n³ < n⁴ < 2ⁿ < nⁿ

Now let's talk about Notations.

There are three types of Notations (mainly):

• BIG O Notation
• BIG OMEGA Notation (Ω) and
• BIG THETA Notation (Θ)

Let's check each one by one...

Big O Notation:

Okay so consider, you have 2 algorithms, one which takes 10 iterations and the other which takes 20 iterations, no issues on that both will have almost the same efficiency, but when it comes to 10 iterations and 1000 iterations, then it is a matter of concern.

The Big O notation, where O stands for 'order of' is concerned with what happens for the huge values of n. For example, if sorting the algorithm performs n*n operations to sort just n elements, then that the algorithm would be described as O(n*n) algorithm. 

When expressing complexity using Big O notation, constant multipliers are ignored. That means an O(4n) is equivalent to O(n). 

If f(n) and g(n) are the functions defined on a positive integer number n, then

f(n) = O(g(n))  --- read as 'f of n is Big O of g of n'

and this is possible if and only if positive constants c and n exists, such that

f(n) ≤ cg(n)

It means that for a large amount of data, f(n) will grow no more than a constant factor than g(n). Hence g provides an upper bound.

Note that here c is a constant which depends on the following factors:

• the programming language used,
• the quality of the compiler or interpreter,
• the knowledge of programmer,
• the size of the main memory and the access time to it,
• the CPU speed, and
• the algorithm itself.

Point to remember: the Big O notation provides a strict upper bound for f(n). That means that function f(n) can do better but not worse then the specified value.

Mathematically speaking, 

        If f(n) ≤ cg(n), c > 0,∀ n ≥ n₀, then f(n) = O(g(n)) and g(n) is an asymptotically tight upper bound for f(n). 

Example of function in O(n³) include n^2.9, n³, n³ + n, 540n³ + 10.

And the examples which not comes in O(n³): n^3.2, n², n²+ n, 540n + 10, 2n.

Big O Notation: f(n) ≤ c g(n)

Categories of Algorithms:

A/c to Big O we have five different categories of algorithms...

• Constant time algorithm: O(1)
• Linear time algorithm: O(n)
• Logarithmic time algorithm: O(log n)
• Polynomial-time algorithm: O(n^k) where k > 1
• Exponential time algorithm: O(2ⁿ).

Limitations of Big O Notation: 

• Many algorithms are simply too hard to analyze mathematically.
• There may not be sufficient information to calculate the behavior of an algorithm in the average class.
• Big O analysis only tells us how the algorithm grows with the size of the problem, not how efficient it is, as it does not consider the programming effort. 
• It ignores important constants. 

Omega Notation (𝛀):

The Omega notation provides a tight lower bound for f(n). This means that the function can ever do better than the specified value but it may be worse.

Ω notation is simply written as f(n) ∈ Ω(g(n)), where n is the problem size and 

Ω(g(n)) = {h(n): ∃ positive constant c > 0, n_o such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n₀}.

Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n_o.

If cg(n) ≤ f(n), c < 0, ∀ n ≥ n_o, then f(n) ∈ Ω(g(n)) and g(n) is an asymptotically tight lower bound. 

Examples of  functions in Ω(n²) include: n², n³+n², n³, n^2.9

Examples of functions not in Ω(n³) include: n², n^2.9, n

Omega Notation: f(n) ≥ c g(n)

To summarize,

• Best Case Ω describes a lower bound for all combinations of input.
• Worst case Ω describes a lower bound for worst-case input combinations.
• If we simply write Ω,  it means the same as best-case Ω.

Theta Notation (Ө):

Theta notation provides an asymptotically tight bound for f(n). Ө notation is simply written as, f(n) ∈ Ө(g(n)), where n is the problem size and 

Ө(g(n)) = {h(n): ョpositive constant c₁, c₂, and n₀ such that 0 ≤ c₁g(n) ≤ h(n) ≤ c₂g(n), ∀ n ≥ n₀}.

Hence, we say that Ө(g(n)) comprises a set of all the functions h(n) that are between c₁g(n) and c₂g(n) for all values of n ≥ n₀.

Theta Notation: c₂ g(n) ≤ f(n) ≤ c₁ g(n)

To summarize,

• The best case in Ө notation is not used.
• Worst case Ө describes asymptotic bounds for the worst-case combination of input values.
• If we simply write Ө, it means the same as worst-case Ө.

In the upcoming post, we will be calculating the complexities of the expressions...

Next: Complexity Analysis in loops

By that,

Harsh Jaiswal

Signing of...

Analysis of Algorithm - 22 Weeks of DSA

DAY - 01 of 22 Weeks

View the plan Here...

Analysis of Algorithm...

The typical definition of an algorithm is 'a formally defined procedure for performing some calculation'. If a procedure is formally defined, then it can be implemented using formal language, and such language is known as a programming language. In general terms, the algorithm provides a blueprint to write a program to solve a particular problem. 

TIME and SPACE Complexity

Analyzing an algorithm means determining the number of resources (such as time and memory) needed to execute it. Algorithms are generally designed to work with an arbitrary number of inputs, so the efficiency or complexity of an algorithm is stated in terms of time and space complexity. 

The time complexity of an algorithm is basically the running time of a program as a function of the input size. Similarly, the space complexity of an algorithm is the amount of computer memory that is required during the program execution as a function of the input size.

The running time/execution time depends on several factors. First, the amount of data that must be processed directly affects the execution time. As the data size increases, so does the execution time. Second, the execution time can vary depending on the type of hardware and the time the computer is used. If we use a multi-process, multi-user system to execute the program, the execution of other programs on the same machine can directly affect the execution time of our program. Finally, the choice of programming language and compiler used to implement an algorithm can also influence the execution time. Some compilers are better optimizers than others and some languages produce better-optimized code than others.

Thus, we need a method to analyze an algorithm's efficiency independent of the implementation details.

Worst-case, Average-case, Best-case, and Amortized Time Complexity

Worst-Case running time: 

• This denotes the behavior of an algorithm with respect to the worst possible case of the input instance.
• This case of an algorithm is an upper bound on the running time for any input.
• Having the knowledge of worst-case gives an assurance that the algorithm will never go beyond this time limit.

Average-Case running time:

• Average-Case running time is an estimate of the running time for an 'average' input. 
• Average-case running time assumes that all inputs of a given size are equally likely.

Best-Case running time:

• This case is used to analyze an algorithm under optimal conditions. For example, the best case for the linear search of an array occurs when the desired element is the first in the list. 
• While selecting an algorithm we hardly base our decision on the best-case performance. 

Amortized running time:

• Amortized running time refers to the time required to perform a sequence of (related) operations averaged over all the operations performed. 
• Amortized analysis guarantees the average performance of each operation in the worst case.

Expressing Time and Space Complexity

The time and space complexity can be expressed using the function f(n) where n is the input size for a given instance of the problem being solved. 

Expressing the complexity is required when 

• We want to predict the rate of growth of complexity as the input size of the problem increases.
• There are multiple algorithms that find solutions to a given problem and we need to find the most efficient algorithm.

Algorithm Efficiency

If a function is linear (without any loops or recursion), the efficiency of that algorithm or running time of that algorithm can be given as the number of instructions it contains.

Algorithm efficiency changes with change in the number of loops. 

Linear Loops

To determine an efficiency of algorithm with single loops, we first need to calculate the number of times the statement in the loops will be executed.

This is because, Number of iteration is directly proportional to the loop factor.

Example:

In C :

for (i = 0; i < 500; i++)
    statement block;

In Python:

for i in range(0, 500):
    statement block

Here, 500 is the loop factor. 

As we know now, efficiency is directly proportional to number of iterations. So, the general formula in the case of linear loop can be written as :

f(n) = n

Nevertheless calculating efficiency is not so simple as in above example.

Consider the given loop...

In C:

for (i = 0; i < 500; i += 2)
    statement block;

In Python:

for i in range(0, 500, 2):
    statement block

Here, the number of iteration is half the number of loop factor. So efficiency is given as,

f(n) = n/2

Logarithmic Loops

Now we know, what are linear loops, they are whose loop updates either by addition or subtraction. Anyway, in logarithmic loops, the loop-controlling variable is either multiplied or divided during each itetration of the loop. As shown below...

In C:

for (i = 1; i < 1000; i *= 2)                for (i = 1000; i >= 1; i/=2)
    statement block;                             statement block;

In Python:

for i in range(1, 1000):                     for i in range(1000, 1, i/2):
    statement block                              statement block

Consider the first for loop in which the loop-controlling variable i is multiplied by 2. The loop is executed only 10 times and not 1000 times because in each iteration the value of i doubles.

And in the second loop in which the loop-controlling variable i is divided by 2. In this case also, the loop will be executed 10 times. 

Thus, the number of iteration is a function of the number by which the loop-controlling variable is divided or multiplied.

That is, when n = 1000, the number of iterations canbe given by log 1000 which is approximately equal to 10.

Therefore, when loop-controlling variable is divided or multiplied then, then efficiency is given as,

f(n) = log n

Nested Loops

Loops inside loops are Nested Loops. To determine the efficiency of Nested loops, we need to calculate the number of times each loop is multiplied after each iteration. The total is then obtained as theproduct of the number of iterations in both loops.

Linear logarithmic loop

Consider the following loops:

In C:

for (i = 0; i < 10; i++)            -- (n) times
    for (j = 1; j < 10; j *= 2)        -- (log n) times
        statement blocks;

In Python:

for i in range(0, 10):            -- (n) times
    for j in range(1, 10):        -- (log n) times
        statement blocks;
        j *= 2;

So, the efficiency is f(n) = n log n.

Quadratic loop

Consider the following loops:

In C:

for (i = 0; i< 10; i++)            -- n times
    for (j = 0; j < 10; j++)        -- n times
        statement block;

In Python:

for i in range(0, 10):                -- n times
    for j in range(0, 10):            -- n times
        statement block

So, the efficiency is f(n) = n^2.

Dependent quadratic loop

In dependent quadratic loop, the number of iterations in the inner loop is dependent on the outer loop. Consider the following loop:

In C:

for (i =0; i < 10; i++)
    for (j = 0; j <= i; j++)
        statement block; 

In Python:

for i in range(0, 10):
    for j in range(0, i+1):
        statement block

So, the efficiency is calculated as:

1+2+3+4+...+9+10 = 55

So, we have f(n) = n (n + 1) / 2

Next: Asymptotic Notation

See you in the next post.

Its Harsh Jaiswal

Signing off...

A Perfect Plan for Data Structure and Algorithm | Python & C Language

 

A Perfect Plan...

...22 Weeks of DSA...

This is the Perfect Plan for learning Data Structure and Algorithm in C and Python...

Make your 2021 more productive than ever...

Download this PDF for understanding this Plan.

Click Here

(to access the pdf)

The Practice Problems will be from different coding platforms like HackerEarth, HackerRank, CodeChef, GFG, and many more.

The explanation of every topic will be uploaded every week...

Links will be available as I upload the posts on topics

The Weekly Topics are:

Week 1: Introduction and Mathematics

Week 2: Bit Magic

Week 3: Recursion

Week 4: Arrays

Week 5: Searching

Week 6: Sorting

Week 7: Matrix

Week 8: Hashing

Week 9: Strings

Week 10: Linked Lists

Week 11: Stack

Week 12: Queue and Deque

Week 13: Tree

Week 14: Binary Search Tree

Week 15: Heap

Week 16: Graph

Week 17: Greedy

Week 18: Back Tracking

Week 19, 20: Dynamic Programming

Week 21: Trie

Week 22: Segement Tree and Disjoint Set 

Let's work hard and put our 1st Step towards Competitive Programming...

Meet you on 1st Jan 2021...

Harsh Jaiswal

Signing off...