DEV Community: Abhishek Chandra

Asymptotic Notations

Abhishek Chandra — Fri, 09 Jul 2021 16:24:37 +0000

The objective of this article is to explain Analysis of Algorithms and Asymptotic Notations i.e. Big-O, Omega-Ω, and Theta-Θ. These topics are the most basic foundation for Data Structures and Algorithms.

Analysis of Algorithms

The idea of analysis of algorithms is to compare algorithms mainly in terms of running time and space consumed.
For example,
To go from city 'M' to city 'Z', there can be many ways to carry-out this task: by flight, by bus, by train and also by bicycle. Depending on the accessibility and convenience, we choose the one that suits us. Similarly, in computer science we have various algorithms available for solving a same problem, for example we can solve sorting problem by many algorithms like selection-sort, bubble-sort, merge-sort and many more but we will choose the one with lesser complexity. (Best algorithm for sorting is quick-sort with complexity O(nlog(n)) )

This concludes that Analysis of Algorithm should be used in determining which method is more efficient and also which method is good in terms of time and space consumed.

Prior to learning Asymptotic Notations, Let's see what is rate of growth of an algorithm.

Rate of growth is nothing but the rate at which the run time complexity of the algorithm increases as a function of the input.

Let's suppose we have to purchase a laptop and a mouse. If someone asks you what are you purchasing, then in general you will say buying a laptop and ignore buying the mouse part. This is because, cost of laptop is too big compared to cost of mouse. So, we can say

Total Cost = cost_of_laptop + cost_of_mouse

Total Cost ≈ cost_of_laptop (approximately)

For the above mentioned example, we can represent the cost of laptop and cost of mouse as a function and for a given function, we can ignore the lower order terms (that are relatively insignificant for large value of input size, n). Let us consider another example in terms of algebra, let n⁴, n², 100n and 5 are individual costs of some function, here we can approximate this function to n⁴ i.e. the highest rate of growth.

n⁴ + n² + 100n + 5 ≈ n⁴

Here's the list of most common rate of growths.

Time Complexity	Name	Example
1	Constant	accessing an array element
log(n)	Logarithmic	finding an element in a sorted array
n	Linear	finding an element in a unsorted array
nlog(n)	Linear Logarithmic	sorting n items with divide-and-conquer (Merge Sort)
n²	Quadratic	shortest path between two nodes in a graph
n³	Cubic	matrix multiplication
2ⁿ	Exponential	tower of hanoi problem

Before going to Asymptotic Notations, We also need to know about Types Of Analysis.

Types of Analysis

If we have to analyse an algorithm, we need to know on what inputs the algorithm takes less time, and on what inputs the algorithm is taking more time. That means we can represent algorithms with multiple expressions: one for the case where it takes less time and other for the case where it takes more time.

In general, when the algorithm takes less time it is called as the best case and when the algorithm takes more time than it is called as the worst case.
To analyse an algorithm we need some kind of syntax and that forms the base for asymptotic analysis / notation.
There are three types of analysis:

Worst Case

defines the input for which algorithm takes longest time to execute.
algorithm runs slower.
algorithm which executes maximum number of steps on input data of size n.

Best Case

defines the input for which algorithm takes lowest time to execute.
algorithm runs fastest.
algorithm which executes least number of steps on input data of size n.

Average Case

provides a prediction about the running time of the algorithm.
assumes that the input is random.
algorithm which performs average number of steps on input data of size n.

Lower Bound <= Average Time <= Upper Bound

Asymptotic Notations

Asymptotic Notations is having an expressions for the best, average and worst cases, for all the three cases we need to identify the upper and lower bounds. To represent these upper and lower bounds we need some kind of syntax and that is the following discussion. Let us assume that for a given algorithm, it can be represented in the form of function f(n).

Big - O Notation :

This notation gives the tight upper bound of the given algorithm / function f(n). It is represented as

f(n) = O(g(n)).

It means, for larger values of n, the upper bound of function f(n) is a function g(n).

Here upper bound means, value of f(n) cannot exceed g(n) after a particular value of n. (represented as n0 in the graphical approach).

Let's see this with a graphical approach.

After n = n0, value of g(n) is always greater than or equal to the given algorithm's rate of growth f(n).

Also, for example, if f(n) = n⁴ + 100n + 50 is the given algorithm, then n⁴ is g(n). That means, g(n) = n⁴ gives the maximum rate of growth for f(n) at larger values of n.

O-Notation can be also be defined as O(g(n)) = { f(n) : there exists positive constant c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }.

Our objective is to get smallest rate of growth g(n) which is greater than or equal to f(n)'s rate of growth.

Generally we discard lower values of n. That means the rate of growth at lower values of n is not important. In the graph, n0 is the point from which we need to consider the rate of growths for a given algorithm. Below n0 the rate of growths could be different.

Some Big - O Examples:

f(n) = n² + 1

n² + 1 ≤ 2n², for all n ≥ 1

Therefore, n² + 1 = O(n²), with c = 2 and n0 = 1

f(n) = 2n³ - 2n²

2n³ - 2n² ≤ 2n³, for all n ≥ 1

Therefore, 2n³ - 2n² = O(2n³), with c = 2 and n0 = 1

There is one more thing related to values of n0 and c, that is, there is no isolated set of values for n0 and c in finding the asymptotic bounds. Let us see an example,
100n + 5 = O(n). For this function, there can be multiple values for n0 and c, giving us an asymptotic solution / bound.

Solution 1: 100n + 5 ≤ 100n + n = 101n, for all n ≥ 5, n0 = 5 and c = 101.

Solution 2: 100n + 5 ≤ 100n + 5n = 105n, for all n ≥ 1, n0 = 1 and c = 105.

Both possibilities are correct.

Note : Most of the time we are interested in knowing the Big - O Notation i.e. Tight Upper Bound of an algorithm because it allows us to estimate weather an algorithm is feasible for our application or not, by telling us that this algorithm will not take more than such-and-such amount of memory or time when run on an input of size n.

Omega - Ω Notation :

This notation gives the tight lower bound of the given algorithm / function f(n). We can represent it as

f(n) = Ω(g(n))

It means, for larger values of n, g(n) is the lower bound of function f(n).

Here lower bound means, rate of growth of f(n) is always greater than or equal to the rate of growth of function g(n) after a particular value of n i.e. n0.

Let's see this with a graphical approach.

After n = n0, value of g(n) is always smaller than or equal to the given algorithm's rate of growth f(n).

Ω Notation can also be defined as Ω(g(n)) = { f(n) : there exists positive constants n0 and c such that* 0 ≤ cg(n) ≤ f(n) * for all n ≥ n0 }.

Here, our objective is to get largest rate of growth g(n) which is less than or equal to f(n)'s rate of growth. g(n) is asymptotic lower bound for the given algorithm's rate of growth f(n).

Some Ω Examples :

f(n) = 5n²

∃ (there exists) c, n0, such that: 0 ≤ cn ≤ 5n² => c = 1 and n0 = 1

Therefore, 5n² = Ω(n²)

2n = Ω(n), n³ = Ω(n³), logn = Ω(logn)

*Note : * Lower bounds are of great use as well. Lower bounds can give information about whether we can improve our algorithm or is it feasible. We can also know that our algorithm is optimal, if our lower bound is equal to the upper bound.

Theta - Θ Notation :

This notation gives a range of upper bound and lower bound and determines whether the upper bound and lower bound of the given algorithm are same. The average running time of an algorithm is always between the lower bound (Omega - Ω) and upper bound (Big - O) of the function. If the upper bound and lower bound of a function gives the same result (rate of growth) then Theta - Θ will also have the same rate of growth.

For example, assume f(n) = 10n + n, then its tight upper bound is O(n) and the lower bound is Ω(n).
In this case, rate of growths in the best case and worst case are same. As a result, the average case will also be the same.
If for a given algorithm, the rate of growths O and Ω are not same then the rate of growth for Θ may not be same. In this case, we have to consider all possible time complexities and take average of those. (for example, quick sort average case gives Θ(nlogn) complexity)

Let us also see this in a graphical approach.

After n = n0, the value of f(n) is always between c2g(n) and c1g(n).

Θ Notation can also be defined as Θ(g(n)) = { f(n) : there exists positive constants c1, c2, and n0 such that* 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) , for all n ≥ n0 }. g(n) is an asymptotic tight bound for f(n).

Θ(g(n)) is a set of functions with same order of growth as g(n).

Some Θ Examples:

Prove n ≠ Θ(n²)

c1n² ≤ n ≤ c2n², only holds for n ≤ 1 /
c1

Therefore, n ≠ Θ(n²)

Prove 6n³ ≠ Θ(n²) c1n² ≤ 6n³ ≤ c2n², only holds for n ≤ c2 / 6

Therefore, 6n³ ≠ Θ(n²)

Why is it called Asymptotic Notations?

For all the three notations, O, Ω, Θ, in every case for a given function f(n) we are trying to find other function g(n) which approximates f(n) at large values of n. That means, g(n) is also a curve which approximates f(n) at large values of n.

In mathematics, we call such curves as asymptotic curves. In other terms, g(n) is the asymptotic curve for f(n). For this reason, we call algorithm analysis as asymptotic analysis and notations as asymptotic notations

Properties of Notations:

Transitivity : f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then f(n) = Θ(h(n)). Valid for O and Ω as well.
Reflexivity : f(n) = Θ(f(n)). Valid for O and Ω as well.
Symmetry : f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).
Transpose symmetry : f(n) = O(g(n)) if and only if g(n) = Ω(f(n)).

Bonus :

Master Theorem for Divide and Conquer

All divide and conquer algorithms works by dividing the problem into sub-problems, each of which is part of the original problem and then we perform some additional work to compute the final answer. As an example, merge sort algorithm operates on two sub problems, each of which is half the size of the original problem and then performs O(n) additional work for merging the sub-problems.

This gives the running time of the equation :

T(n) = 2T(n / 2) + O(n)

Master theorem can be used to determine the running time of divide and conquer algorithms. For a given algorithm, first we try to find the recurrence relation of the problem. If the recurrence relation is of the below form then we can directly give the answer without fully solving it.

If the recurrence relation is of the form, ** T(n) = aT(n / b) + Θ(n^klog^pn)**, where a ≥ 1, b > 1, k ≥ 0 and p is a real number, then:

If a > b^k, then T(n) = Θ(n^{log^ab})
If a = b^k

If p > -1, then T(n) = Θ(n^{log^ab}log^p+1n).
If p = -1, then T(n) = Θ(n^{log^ab}loglogn).
If p < -1, then T(n) = Θ(n^{log^ab})

If a < b^k

If p ≥ 0, then T(n) = Θ(n^klog^pn)
If p < 0, then T(n) = O(n^k)

Thank You!

Templates in C++

Abhishek Chandra — Sat, 03 Jul 2021 13:48:08 +0000

Templates in C++ Language

The keyword template is used to define function templates and class templates in our C++ program.
It introduces generic programming, which makes a way for programmers to write more efficient code.

So, now there are two ways in which we can use template,

Function template

Function template is also known as generic function.

syntax creating function template:

template<class type> 
type func_name(type arg1, type arg2, ....){
     ...
};
// here type is a placeholder for generalisation of data type.

It creates a function template named func_name with any number of arguments.

Let's learn this with an example,

Program to find the smaller number from the given two numbers* without the use of template*:

#include<iostream>

using namespace std;

// without the use of template keyword.
int small(int a, int b){
    if(a > b){
        return(b);    
    }else{
        return(a);
    }
};

double small(double a, double b){ // function overloading
    if(a > b){
        return(b);
    }else{
        return(a);
    }
};


int main(){
    cout<<small(2,6)<<endl;
    cout<<small(2.4,1.9);
    return 0;
}

/*
OUTPUT
2
1.9
*/

(32 Lines of Code)

To avoid using different data types in a function, Use template.

#include<iostream>

using namespace std;

// Program using template keyword
template<class X>
X small(X a, X b){ // here X is a generic data type, making 'small' a generic function.
    if(a < b){
        return(b);
    }else{
        return(a);
    }
};

int main(){
    cout<<small(3,4)<<endl;
    cout<<small(3.4,1.6); // no function overloading reduces the lines of code in a program
    return 0;
}

/*
OUTPUT
3
1.6
*/

(25 Lines of Code)

Example 2:

template<class X, class Y>  
X big(X a, Y b){        //different data types
    if(a > b){
        return a;
    }else{
        return b;
    }
};

int main(){
    cout<<big(4,3.4)<<endl;
    cout<<big(1.99,-5);
    return 0;
}

/*
OUTPUT:
4
1.99
*/

(20 Lines of Code)

Class template

Class template is also known as generic class.

template<class type> 
class class_name{
    ...
};
// here type is also a placeholder to generalise a class.

It creates a class template named class_name.

Let's also learn this with an example,
Here we are making a arrayList class without the use of template.

#include<iostream>

using namespace std;

class arrayList{
    private:
        struct controlBlock{
            int capacity;
            int *arr_ptr;
        };

    controlBlock *s;

    public:
        arrayList(int capacity){ // constructor of arrayList class
            s = new controlBlock;
            s -> capacity = capacity;
            s -> arr_ptr = new int[s->capacity];
        }
        void addElement(int index, int data){ // method to add elements to the list
            if(index >= 0 && index <= s->capacity - 1){
                s -> arr_ptr[index]  = data;
            }else{
                cout<<"Array index not valid";
            }
        }
        void viewElement(int index, int &data){
            if(index >=0 && index <= s->capacity - 1){
                data = s->arr_ptr[index];
            }else{
                cout<<"Array index not valid";
            }
        }
        void viewList(){ // method to view the list
            int i;
            for(i = 0; i < s->capacity; i++){
                cout<<" "<<s->arr_ptr[i];
            }
        }
};

int main(){
    int data;
    arrayList list1(4);
    list1.addElement(0,2);
    list1.addElement(1,12);
    list1.addElement(2,22);
    // list1.addElement(3,32); if not assigned, by default 0 is assigned.
    // list1.viewElement(0,data);
    // cout<<data;
    list1.viewList();
    return 0;
}

/*
OUTPUT:
2
12
22
0
*/

(61 Lines of Code)

Image explanation of code.

Now, templating our above program will result in increased possibilities of input with the same number of lines of code.

visit : arrayList_with_template.cpp

Go read about STL in this article.

Standard Template Library in C++

Abhishek Chandra — Thu, 10 Jun 2021 17:39:20 +0000

vector<int> LET_S;
pair<string, int> GET;
list<int> STARTED;
array<int, 3> WITH;
map<int, string> STL;

Still don't know what these statement do?

Let's read this article to head start your journey in STL.

Standard Template Libraries are powerful set of C++ template classes. It contains numerous pre-defined classes and are used to make programming easier.

Consider Standard Template Libraries as a helping hand for not writing codes to implement Data Structures like Linked Lists, Stacks, Queues, Trees etc. in every program we require them (mostly in competitive programming questions), we can use these data structures by just including a library and using a pre-defined syntax.

Also, classes in Standard Template Libraries are made through template classes so these are generic in nature.

At the core of the C++ Standard Template Libraries, these are the following three well structured components.

Containers.
Algorithms.
Iterators.

Containers

Containers are used to manage and store collection of objects of a certain kind.
Container Library in STL provide containers that are used to create data structure like arrays, linked-list, trees, etc.
Containers helps us to implement and replicate simple and complex data structures very easily like array, list, trees, associative arrays and many more.
These containers are generic in nature, they can hold elements of any data types.

Common Containers that replicates simple and complex data structures

vector : replicates arrays
queue : replicates queues
stack : replicates stack
priority_queue : replicated heaps
list : replicates linked list
set : replicates trees
map : associative arrays

Classification of containers

Sequence Containers : These containers hold linear storage of data, like arrays, linked list etc.
Associative Containers : Ordered containers like map, multimap, set, multiset are associative containers. (Ordered means the values are stored in the respective container in the same order as inputted by the user)
Unordered Associative Containers : These are similar to associative containers but have different constraints, the elements are stored unordered due to the use of hash tables while implementing these containers.

How to use containers?

When we use containers to implement data structures, we just have to include a header file and use the respective syntax to initialise the data structure you need.

#include<bits/stdc++.h>

or you can just include a specific container header file,

#include<iostream>

// importing vector header file to implement vectors
#include<vector>

int main(){
 vector<int> first_vector;
 return 0;
}

// vector can be used for creating dynamic arrays of `char`, `int`, `float` and other types.

#include<iostream>

//  importing list header file to implement lists
#include<list>

int main(){
 list<int> my_list;
 return 0;
}

Algorithms

Algorithms act on containers. They provide the means by which you will perform initialization, sorting, searching, and transforming of the contents of container.
Algorithms Library contains built-in functions that perform complex algorithms on the data structures.

Example:

We can reverse a range with reverse() function, sort a range with sort() function, search on a range with binary_search() and so on.
Algorithm Libraries provide abstraction, i.e. you don't necessarily need to know how the algorithm works.

Sorting of a vector

#include<bits/stdc++.h>

using namespace std;

int main(){
 vector<int> second_vector {44,22,66,33,99};

// begin() and end() method returns an iterator to the vector.
 sort(second_vector.begin(), second_vector.end());
 return 0;
}

/* 
Above code will sort the vector to {22,33,44,66,99}.
More about vector will be covered in a separate node.
*/

Iterators

Iterators are used to step through the elements of collection of objects. These collections can be containers or subsets of containers.
Iterators in Standard Template Libraries are used to point to the containers.
Iterators actually acts as a bridge b/w containers and algorithms.

Let's look at the above code in algorithms section for reference to iterators,

sort() algorithm or function have two parameters, starting iterator (vector.begin()) and ending iterator (vector.end()) pointing to first and last element in the vector respectively, now sort() compares the elements pointed by each of these iterators and arrange them in sorted order, thus it does not matter what is the type of the container and same sort can be used on different types of containers.

How to declare an iterator?

Syntax

// This is an iterator of type vector
vector<int> :: iterator itr; 
// itr is the iterator

Example use of iterator:

Printing elements of a vector

#include<bits/stdc++.h>

using namespace std;

int main(){
    vector<int> third_vector {10,20,30,40,50};
    vector<int> :: iterator itr;
    for(itr = third_vector.begin(); itr != third_vector.end(); itr++){
        cout<<*itr<<" ";
    }
    return 0;
}

/*
OUTPUT : 10 20 30 40 50 
*/

Visit this to view some Standard Template Libraries programs.

Strings in C++

Abhishek Chandra — Sat, 13 Mar 2021 15:44:48 +0000

Youkoso!

Here's Traditional Way (C Language)

We use null-terminated (\0) character array, although it is not technically a data type.
So, Operators cannot be applied to them, like assignment and comparison operators =, <, >, <=, >=.

// Declaration of character array
char s1[10], s2[10];
s1[10] = "Doge";

// Error Full Code (Don't use at home/work)
s2 = s1;
s2 > s1;
s3 = s1 + s2;

This code results in invalid array operations.

Strings in C++

The string class is a expertise class of a more general template called basic_string.
Since defining a class in C++ is creating a new data type, string is derived data type.
This means operators can be overloaded for this class.

syntax

class string{
   // Variables
   // functions
   // operators
}

string s1;
s1.function();
s1.operator(arguments);

string operations are safe but time consuming. So, 'char array' (speedy, less operations) concept is not deprecated.

if (speed matters) {
Use character array
}else if (safety and easy manipulation matters) {
Use string class
}

Here's why string is safer than character array

Careful programmers like you, can overrun to the end of an array that holds a null terminated (null character \0) string.
for example - see below
string class handles such issues.

char s3[10];
strcpy(s3,"Hello careful programmers.");

String is also in STL (but concept of string is thought apart from STL concepts)

string is an another container class.
To use string class, we have to include string header class. (not string.h)
- #include<string> (for string header class)
- #include<string.h> (in C, for string functions applied on character array)

String class supports many constructors as follows.

string()
string(const char *str)
string(const string &str)

Operators

= (assignment)
+ (concatenation)
+= (concatenation assignment)
== (equality)
!= (inequality)
< (less than)
<= (less than equal to)
> (greater than)
>= (greater than equal to)
[] (subscripting)
<< (insertion)
>> (extraction)

Mixed Operations

We can mix string objects with another string object or C style string.
C++ string can also be concatenated with character const.

Useful methods

assign()
append()
insert()
replace()
erase()
find()
rfind()
compare()
c_str()
size()

Visit :

ittekimasu! :)

DEV Community: Abhishek Chandra

Asymptotic Notations

Analysis of Algorithms

Types of Analysis

Asymptotic Notations

Big - O Notation :

Some Big - O Examples:

Omega - Ω Notation :

Some Ω Examples :

Theta - Θ Notation :

Some Θ Examples:

Why is it called Asymptotic Notations?

Properties of Notations:

Bonus :

Master Theorem for Divide and Conquer

Templates in C++

Templates in C++ Language

Function template

Class template

Standard Template Library in C++

Containers

Common Containers that replicates simple and complex data structures

Classification of containers

How to use containers?

Algorithms

Iterators

How to declare an iterator?

Strings in C++

Here's Traditional Way (C Language)

Strings in C++

syntax

String is also in STL (but concept of string is thought apart from STL concepts)

String class supports many constructors as follows.

Operators

Mixed Operations

Useful methods

Visit :