notes_stuff

This repo is snapshots of differencet book to have them accessible in nicely organized manner.

View on GitHub

Types of Asymptotic Notations in Complexity Analysis of Algorithms

We have discussed Asymptotic Analysis, and Worst, Average, and Best Cases of Algorithms. The main idea of asymptotic analysis is to have a measure of the efficiency of algorithms that don’t depend on machine-specific constants and don’t require algorithms to be implemented and time taken by programs to be compared. Asymptotic notations are mathematical tools to represent the time complexity of algorithms for asymptotic analysis.

**Asymptotic Notations:**

**There are mainly three asymptotic notations:**

  1. **Big-O Notation (O-notation)**
  2. **Omega Notation (Ω-notation)**
  3. **Theta Notation (Θ-notation)**

  1. Theta Notation (Θ-Notation):

Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the **average-case** complexity of an algorithm.

.Theta (Average Case) You add the running times for each possible input combination and take the average in the average case.

Let g and f be the function from the set of natural numbers to itself. The function f is said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

Theta notation

**Mathematical Representation of Theta notation:**

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}

**Note:** Θ(g) is a set

The above expression can be described as if f(n) is theta of g(n), then the value f(n) is always between c1 * g(n) and c2 * g(n) for large values of n (n ≥ n0). The definition of theta also requires that f(n) must be non-negative for values of n greater than n0.

**The execution time serves as both a lower and upper bound on the algorithm’s time complexity.**

**It exist as both, most, and least boundaries for a given input value.**

A simple way to get the Theta notation of an expression is to drop low-order terms and ignore leading constants. For example**,** Consider the expression **3n**3** **+ 6n**2** **+ 6000 = Θ(n**3**)**, the dropping lower order terms is always fine because there will always be a number(n) after which Θ(n3) has higher values thanΘ(n2) irrespective of the constants involved. For a given function g(n), we denote Θ(g(n)) is following set of functions. 

**Examples :**

{ 100 , log (2000) , 10^4 } belongs to **Θ(1)**
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to **Θ(n)**
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to **Θ( n**2**)**

**Note: Θ provides exact bounds.**

**2. Big-O Notation (O-notation)**:**

Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-case complexity of an algorithm.

.It is the most widely used notation for Asymptotic analysis.
.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-Oh(Worst Case) It is defined as the condition that allows an algorithm to complete statement execution in the longest amount of time possible.

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

**It returns the highest possible output value (big-O)for a given input.**

**The execution time serves as an upper bound on the algorithm’s time complexity.**

BigO

**Mathematical Representation of Big-O Notation:**

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

For example**,** Consider the case of Insertion Sort. It takes linear time in the best case and quadratic time in the worst case. We can safely say that the time complexity of the Insertion sort is O(n2). 
**Note**: O(n2) also covers linear time. 

If we use Θ notation to represent the time complexity of Insertion sort, we have to use two statements for best and worst cases: 

The Big-O notation is useful when we only have an upper bound on the time complexity of an algorithm. Many times we easily find an upper bound by simply looking at the algorithm.  

 **Examples :**

{ 100 , log (2000) , 10^4 } belongs to **O(1)**
**U** { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to **O(n)**
**U** { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to **O( n^2)**

**Note:** Here, **U represents union, we can write it in these manner because **O provides exact or upper bounds .**

  1. Omega Notation (Ω-**Notation)**:**

Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case complexity of an algorithm.

**The execution time serves as a lower bound on the algorithm’s time complexity.**

**It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount of time.**

Let g and f be the function from the set of natural numbers to itself. The function f is said to be Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥ n0

BigOmega

**Mathematical Representation of Omega notation :**

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

Let us consider the same Insertion sort example here. The time complexity of Insertion Sort can be written as Ω(n), but it is not very useful information about insertion sort, as we are generally interested in worst-case and sometimes in the average case. 

**Examples :**

{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to **Ω( n^2)**
**U** { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to **Ω(n)**
**U** { 100 , log (2000) , 10^4 } belongs to **Ω(1)**

**Note:** Here, **U represents union,** we can write it in these manner because **Ω provides exact or lower bounds.**

**Properties of Asymptotic Notations:**

**1. General Properties:**

If **f(n)** is **O(g(n))** then **a*f(n)** is also **O(g(n)), where **a** is a constant.

**Example:**

f(n) = 2n²+5 is O(n²) 
then, 7*f(n) = 7(2n²+5) = 14n²+35 is also O(n²).

Similarly, this property satisfies both Θ and Ω notation.

**We can say,**

If f(n) is Θ(g(n)) then a*f(n) is also Θ(g(n)), where a is a constant. 
If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)), where a is a constant.

**2. Transitive Properties:**

If **f(n)** is **O(g(n))** and **g(n)** is **O(h(n))** then **f(n) = O(h(n))**.

**Example:**

If f(n) = n, g(n) = n² and h(n)=n³
n is O(n²) and n² is O(n³) then, n is O(n³)

Similarly, this property satisfies both Θ and Ω notation.

**We can say,**

If f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) = Θ(h(n)) .
If f(n) is Ω (g(n)) and g(n) is Ω (h(n)) then f(n) = Ω (h(n))

**3. Reflexive Properties**:

Reflexive properties are always easy to understand after transitive.
If f(n) is given then f(n) is O(f(n)). Since MAXIMUM VALUE OF f(n) will be f(n) ITSELF!
Hence x = f(n) and y = O(f(n) tie themselves in reflexive relation always.

**Example:**

f(n) = n² ; O(n²) i.e O(f(n))
Similarly, this property satisfies both Θ and Ω notation.

**We can say that,**

If f(n) is given then f(n) is Θ(f(n)).
If f(n) is given then f(n) is Ω (f(n)).

**4. Symmetric Properties:**

If **f(n)** is **Θ(g(n))** then **g(n)** is **Θ(f(n))**.

**Example:**

If(n) = n² and g(n) = n²
then, f(n) = Θ(n²) and g(n) = Θ(n²)

This property only satisfies for Θ notation.

**5. Transpose Symmetric Properties:**

If **f(n)** is **O(g(n))** then **g(n)** is **Ω (f(n))**.

**Example:**

If(n) = n , g(n) = n²
then n is O(n²) and n² is Ω (n) 

This property only satisfies O and Ω notations.

**6. Some More Properties:**

  1. If **f(n) = O(g(n))** and **f(n) = Ω(g(n))** then **f(n) = Θ(g(n))**
  2. If **f(n) = O(g(n))** and **d(n)=O(e(n))** then **f(n) + d(n) = O( max( g(n), e(n) ))**

**Example:**

f(n) = n i.e O(n) 
d(n) = n² i.e O(n²) 
then f(n) + d(n) = n + n² i.e O(n²)

  1. If **f(n)=O(g(n))** and **d(n)=O(e(n))then **f(n) * d(n) = O( g(n) * e(n))**

**Example:**

f(n) = n i.e O(n) 
d(n) = n² i.e O(n²)
then f(n) * d(n) = n * n² = n³ i.e O(n³)
**_______________________________________________________________________________**
**Note:** If  f(n) = O(g(n)) then g(n) = Ω(f(n))

**Important Links :**

For more details, please refer: Design and Analysis of Algorithms.

Previous

Why the Analysis of Algorithm is important?

Next

Worst, Average and Best Case Analysis of Algorithms

Worst, Average and Best Case Analysis of Algorithms ===================================================

In the previous post, we discussed how Asymptotic analysis overcomes the problems of the naive way of analyzing algorithms. But let’s take an overview of the **asymptotic notation** and learn about What is Worst, Average, and Best cases of an algorithm:

**1. Big-O Notation**

We define an algorithm’s **worst-case** time complexity by using the Big-O notation, which determines the set of functions grows slower than or at the same rate as the expression. Furthermore, it explains the maximum amount of time an algorithm requires to consider all input values.

**2. Omega Notation**

It defines the **best case** of an algorithm’s time complexity, the Omega notation defines whether the set of functions will grow faster or at the same rate as the expression. Furthermore, it explains the minimum amount of time an algorithm requires to consider all input values.

**3. Theta Notation**

It defines the **average case** of an algorithm’s time complexity, the Theta notation defines when the set of functions lies in both **O(expression)** and **Omega(expression)**, then Theta notation is used. This is how we define a time complexity average case for an algorithm. 

Measurement of Complexity of an Algorithm

Based on the above three notations of Time Complexity there are three cases to analyze an algorithm:

**1. Worst Case Analysis (Mostly used)**

In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the case that causes a maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x) is not present in the array. When x is not present, the search()function compares it with all the elements of arr[] one by one. Therefore, the worst-case time complexity of the linear search would be **O(n)**.

**2. Best Case Analysis (Very Rarely used)**

In the best-case analysis, we calculate the lower bound on the running time of an algorithm. We must know the case that causes a minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be ?(1) 

**3. Average Case Analysis (Rarely used)**

In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. Sum all the calculated values and divide the sum by the total number of inputs. We must know (or predict) the distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in the array). So we sum all the cases and divide the sum by (n+1). Following is the value of average-case time complexity. 
 

Average Case Time = \sum_{i=1}^{n}\frac{\theta (i)}{(n+1)} = \frac{\theta (\frac{(n+1)*(n+2)}{2})}{(n+1)} = \theta (n)

Which Complexity analysis is generally used?

Below is the ranked mention of complexity analysis notation based on popularity:

**1. Worst Case Analysis:**

Most of the time, we do worst-case analyses to analyze algorithms. In the worst analysis, we guarantee an upper bound on the running time of an algorithm which is good information. 

**2. Average Case Analysis**

The average case analysis is not easy to do in most practical cases and it is rarely done. In the average case analysis, we must know (or predict) the mathematical distribution of all possible inputs. 

**3. Best Case Analysis**

The Best Case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn’t provide any information as in the worst case, an algorithm may take years to run.

Interesting information about asymptotic notations:

A) For some algorithms, all the cases (worst, best, average) are asymptotically the same. i.e., there are no worst and best cases. 

  • **Example:**Merge Sort does ?(n log(n)) operations in all cases.

B) Where as most of the other sorting algorithms have worst and best cases. 

  • **Example 1:** In the typical implementation of Quick Sort (where pivot is chosen as a corner element), the worst occurs when the input array is already sorted and the best occurs when the pivot elements always divide the array into two halves.
  • **Example 2:** For insertion sort, the worst case occurs when the array is reverse sorted and the best case occurs when the array is sorted in the same order as output.

Examples with their complexity analysis:

**1. Linear search algorithm:**

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

// Linearly search x in arr[].
// If x is present then return the index,
// otherwise return -1
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

// Driver's Code
int main()
{
    int arr[] = { 1, 10, 30, 15 };
    int x = 30;
    int n = sizeof(arr) / sizeof(arr[0]);

    // Function call
    cout << x << " is present at index "
         << search(arr, n, x);

    return 0;
}

Output

30 is present at index 2

**Time Complexity Analysis: (In Big-O notation)**

**2.** In this example, we will take an array of length (n) and deals with the following cases :

Below is the implementation of the given problem:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

int getSum(int arr[], int n)
{
    if (n % 2 == 0) // (n) is even
    {
        return 0;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum; //  (n) is odd
}

// Driver's Code
int main()
{
    // Declaring two array one of length odd and other of
    // length even;
    int arr[4] = { 1, 2, 3, 4 };
    int a[5] = { 1, 2, 3, 4, 5 };

    // Function call
    cout << getSum(arr, 4)
         << endl; // print 0 because (n) is even
    cout << getSum(a, 5)
         << endl; // print sum because (n) is odd
}
// This code is contributed by Suruchi Kumari

Output

0
15

**Time Complexity Analysis:**

For more details, please refer: Design and Analysis of Algorithms.

Worst, Average, and Best Case Analysis of Algorithms is a technique used to analyze the performance of algorithms under different conditions. Here are some advantages, disadvantages, important points, and reference books related to this analysis technique:

Advantages:

  1. This technique allows developers to understand the performance of algorithms under different scenarios, which can help in making informed decisions about which algorithm to use for a specific task.
  2. Worst case analysis provides a guarantee on the upper bound of the running time of an algorithm, which can help in designing reliable and efficient algorithms.
  3. Average case analysis provides a more realistic estimate of the running time of an algorithm, which can be useful in real-world scenarios.

Disadvantages:

  1. This technique can be time-consuming and requires a good understanding of the algorithm being analyzed.
  2. Worst case analysis does not provide any information about the typical running time of an algorithm, which can be a disadvantage in real-world scenarios.
  3. Average case analysis requires knowledge of the probability distribution of input data, which may not always be available.

Important points:

  1. The worst case analysis of an algorithm provides an upper bound on the running time of the algorithm for any input size.
  2. The average case analysis of an algorithm provides an estimate of the running time of the algorithm for a random input.
  3. The best case analysis of an algorithm provides a lower bound on the running time of the algorithm for any input size.
  4. The big O notation is commonly used to express the worst case running time of an algorithm.
  5. Different algorithms may have different best, average, and worst case running times.

Reference books:

  1. “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein is a comprehensive guide to algorithm analysis, including worst, average, and best case analysis.
  2. “Algorithm Design” by Jon Kleinberg and Éva Tardos provides a modern approach to algorithm design, with a focus on worst case analysis.
  3. “The Art of Computer Programming” by Donald Knuth is a classic text on algorithms and programming, which includes a detailed discussion of worst case analysis.
  4. “Algorithms Unlocked” by Thomas H. Cormen provides a gentle introduction to algorithm analysis, including worst, average, and best case analysis.