I.

Introduction to Algorithms and Data Structures

●​ Data Structure: A method of organizing, managing, and storing data in a way
that allows for efficient access and modification. Examples include arrays, linked
lists, stacks, queues, trees, and graphs.

●​ Algorithm: A finite set of clear, step-by-step instructions or a procedure designed

to solve a specific problem or accomplish a task. Algorithms are
language-independent and form the core logic of programs.

●​ Relationship: Data structures are the foundation on which algorithms operate.

An efficient algorithm often relies on choosing the best data structure for the job
to manage data effectively.

II. Characteristics and Representation of Algorithms

Every algorithm should satisfy the following criteria:
●​ Input: Zero or more values supplied externally.

●​ Output: At least one value produced.

●​ Definiteness: Each instruction must be clear, precise, and unambiguous.

●​ Finiteness: The algorithm must terminate after a finite number of steps for all
test cases.

●​ Correctness/Effectiveness: Every step must be feasible and generate a correct

output, leading to the desired result.

Algorithms can be represented using:

●​ Natural Language: Simple English descriptions (can sometimes be ambiguous).

●​ Pseudocode: A mix of English and structured code syntax, easy to read and
understand without strict programming language rules.

●​ Flowchart: A graphical representation using symbols to show the sequence of

operations.

III. Algorithm Analysis (Efficiency)

The performance of an algorithm is primarily measured by its time and space
complexity.
 ●​ Time Complexity: Measures the amount of time an algorithm takes to run as a
function of the input size, often counted by the number of key operations (e.g.,
comparisons in sorting).

●​ Space Complexity: Measures the amount of memory space required by the

algorithm during execution (for variables, instructions, etc.).

●​ Big O Notation: A mathematical notation used to describe the limiting behavior

of the time or space complexity, focusing on the worst-case scenario or upper
bound as the input size grows (e.g., O(n), O(n log n), O(n²)).

IV. Common Algorithms in Introductory Courses

Introductory courses cover various algorithms, often in the context of the data structures
they manipulate.
●​ Searching Algorithms:

o​ Linear Search: Checks each element sequentially until a match is found.

o​ Binary Search: Efficiently finds an item in a sorted array by repeatedly

dividing the search interval in half (uses the Divide and
Conquer technique).

●​ Sorting Algorithms: Rearrange elements in a specific order.

o​ Bubble Sort: Repeatedly compares and swaps adjacent elements.

o​ Selection Sort: Selects the smallest element and places it at the

beginning of the list.

o​ Insertion Sort: Inserts an unsorted element at its suitable place within the
already sorted part of the list.

o​ Merge Sort: Uses the Divide and Conquer approach; divides the list into
halves, sorts them, and merges the sorted halves.

o​ Quick Sort: Another Divide and Conquer algorithm that uses a pivot
element to partition the array.

●​ Recursive Algorithms: A function that calls itself to solve a problem by breaking

it into smaller, similar sub-problems (e.g., factorial calculation, tree traversals).

●​ Graph Algorithms:
 o​ Breadth-First Search (BFS): Traverses a graph level by level, typically
using a Queue data structure.

o​ Depth-First Search (DFS): Traverses a graph as deeply as possible

along each branch before backtracking, typically using a Stack data
structure.

V. Key Algorithm Design Techniques

●​ Brute Force: A straightforward approach that tries all possible solutions to find
the best one.

●​ Divide and Conquer: Solves a problem by breaking it into smaller, more

manageable sub-problems, solving them, and combining the results (Merge
Sort, Quick Sort).

●​ Greedy Programming: Builds a solution piece by piece, always picking the

option that provides the most immediate benefit at each step.

●​ Dynamic Programming: Solves complex problems by breaking them into

overlapping sub-problems and storing the results of sub-problems to avoid
redundant calculations (memoization/tabulation).

●​ Asymptotic Analysis
Given two algorithms for a task, how do we find out which one is
better?
One naive way of doing this is - to implement both the algorithms and run the
two programs on your computer for different inputs and see which one takes
less time. There are many problems with this approach for the analysis of
algorithms.
●​ It might be possible that for some inputs, the first algorithm performs
better than the second. And for some inputs second performs
better.
●​ It might also be possible that for some inputs, the first algorithm
performs better on one machine, and the second works better on
another machine for some other inputs.

Asymptotic Analysis is the big idea that handles the above

issues in analyzing algorithms. In Asymptotic Analysis, we
evaluate the performance of an algorithm in terms of input
size (we don't measure the actual running time). We
 calculate, order of growth of time taken (or space) by an
algorithm in terms of input size. For example linear search
grows linearly and Binary Search grows logarithmically in
terms of input size.

For example, let us consider the search problem (searching a given item) in a
sorted array.
The solution to above search problem includes:
●​ Linear Search (order of growth is linear)
●​ Binary Search (order of growth is logarithmic).
To understand how Asymptotic Analysis solves the problems mentioned
above in analyzing algorithms,
●​ let us say:
o​ We run the Linear Search on computer A and
o​ Binary Search on computer B and
●​ For small values of input array size n, computer A may take less
time.
●​ But, after a certain value of input array size, the Binary Search will
definitely start taking less time compared to the Linear Search even
though the Binary Search is being run on a slow machine. Why?
After certain value, the machine specific factors would not matter as
the value of input would become large.
●​ The reason is the order of growth of Binary Search with respect to
input size is logarithmic while the order of growth of Linear Search
is linear.
●​ So the machine-dependent constants can always be ignored after
a certain value of input size.
●​ Let’s say the constant for machine A is 0.2 and the constant for B is
1000 which means that A is 5000 times more powerful than B.
Input Size Running time on A Running time on B

2 sec ~1h
10

20 sec ~ 1.8 h
100

~ 55.5 h ~ 5.5 h
10^6

~ 6.3 years ~ 8.3 h

10^9

Running times for this example:

●​ Linear Search running time in seconds on A: 0.2 * n
●​ Binary Search running time in seconds on B: 1000*log(n)
Does Asymptotic Analysis always work?
Asymptotic Analysis is not perfect, but that's the best way available for
analyzing algorithms. For example, say there are two sorting algorithms that
take 1000nLogn and 2nLogn time respectively on a machine. Both of these
algorithms are asymptotically the same (order of growth is nLogn). So, With
Asymptotic Analysis, we can't judge which one is better as we ignore
constants in Asymptotic Analysis. For example, asymptotically Heap Sort is
better than Quick Sort, but Quick Sort takes less time in practice.
Also, in Asymptotic analysis, we always talk about input sizes larger than a
constant value. It might be possible that those large inputs are never given to
your software and an asymptotically slower algorithm always performs
better for your particular situation. So, you may end up choosing an algorithm
that is Asymptotically slower but faster for your software.

Worst, Average and Best Case Analysis of

Algorithms
we discussed how Asymptotic analysis overcomes the problems of the naive
way of analyzing algorithms. Now let us learn about What is Worst, Average,
and Best cases of 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.
●​ This is the most commonly used analysis of algorithms (We will be
discussing below why). Most of the time we consider the case that
causes maximum operations.
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.
●​ For linear search, 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 the order of growth of time taken in terms of
input size is constant.
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). We take (n+1)
to consider the case when the element is not present.
Why is Worst Case Analysis Mostly Used?
Average Case : The average case analysis is not easy to do in most practical
cases and it is rarely done. In the average case analysis, we need to consider
every input, its frequency and time taken by it which may not be possible in
many scenarios
Best Case : The Best Case analysis is considered 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.
Worst Case: This is easier than average case and gives an upper bound
which is useful information to analyze software products.

Asymptotic Notations for Analysis 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:
●​ Asymptotic Notations are mathematical tools used to analyze the
performance of algorithms by understanding how their efficiency
changes as the input size grows.
●​ These notations provide a concise way to express the behavior of an
algorithm's time or space complexity as the input size approaches
infinity.
●​ Rather than comparing algorithms directly, asymptotic analysis
focuses on understanding the relative growth rates of algorithms'
complexities.
●​ It enables comparisons of algorithms' efficiency by abstracting away
machine-specific constants and implementation details, focusing
instead on fundamental trends.
●​ Asymptotic analysis allows for the comparison of algorithms' space
and time complexities by examining their performance
characteristics as the input size varies.
●​ By using asymptotic notations, such as Big O, Big Omega, and Big
Theta, we can categorize algorithms based on their worst-case,
 best-case, or average-case time or space complexities, providing
valuable insights into their efficiency.
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 3n3 + 6n2 + 6000 =
Θ(n3), 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 Θ( n2)

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-O(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.

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 worst-case time complexity of Insertion Sort is Θ(n2).
The best case time complexity of Insertion Sort is Θ(n).
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.

E{ 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 .
2.​ 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
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²)
3. 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))

Time and Space Complexity

:
Many times there are more than one ways to solve a
problem with different algorithms and we need a way to
compare multiple ways. Also, there are situations where we
would like to know how much time and resources an
algorithm might take when implemented. To measure
performance of algorithms, we typically use time and space
complexity analysis. The idea is to measure order of growths
in terms of input size.

Independent of the machine and its configuration, on which

the algorithm is running on.
Shows a direct correlation with the number of inputs.
Can distinguish two algorithms clearly without ambiguity.
Time Complexity: The time complexity of an algorithm
quantifies the amount of time taken by an algorithm to run as
a function of the length of the input. Note that the time to run
is a function of the length of the input and not the actual
execution time of the machine on which the algorithm is
running on.
 The valid algorithm takes a finite amount of time for
execution. The time required by the algorithm to solve given
problem is called time complexity of the algorithm. Time
complexity is very useful measure in algorithm analysis.

It is the time needed for the completion of an algorithm. To

estimate the time complexity, we need to consider the cost of
each fundamental instruction and the number of times the
instruction is executed.

Example 1: Addition of two scalar variables.

Algorithm ADD SCALAR(A, B)

//Description: Perform arithmetic addition of two numbers
//Input: Two scalar variables A and B
//Output: variable C, which holds the addition of A and B
C <- A + B
return C
The addition of two scalar numbers requires one addition operation. the time
complexity of this algorithm is constant, so T(n) = O(1) .
In order to calculate time complexity on an algorithm, it is assumed that
a constant time c is taken to execute one operation, and then the total
operations for an input length on N are calculated. Consider an example to
understand the process of calculation: Suppose a problem is to find whether
a pair (X, Y) exists in an array, A of N elements whose sum is Z. The simplest
idea is to consider every pair and check if it satisfies the given condition or
not.
The pseudo-code is as follows:
int a[n];
for(int i = 0;i < n;i++)
cin >> a[i]

for(int i = 0;i < n;i++)

for(int j = 0;j < n;j++)
if(i!=j && a[i]+a[j] == z)
return true
return false
Below is the implementation of the above approach:

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to find a pair in the given

// array whose sum is equal to z
bool findPair(int a[], int n, int z)
{
// Iterate through all the pairs
 for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)

// Check if the sum of the pair

// (a[i], a[j]) is equal to z
if (i != j && a[i] + a[j] == z)
return true;

return false;
}

// Driver Code
int main()
{
// Given Input
int a[] = { 1, -2, 1, 0, 5 };
int z = 0;
int n = sizeof(a) / sizeof(a[0]);

// Function Call
 if (findPair(a, n, z))
cout << "True";
else
cout << "False";
return 0;
}
Output
False

Assuming that each of the operations in the computer takes

approximately constant time, let it be c. The number of lines
of code executed actually depends on the value of Z. During
analyses of the algorithm, mostly the worst-case scenario is
considered, i.e., when there is no pair of elements with sum
equals Z. In the worst case,

N*c operations are required for input.

The outer loop i loop runs N times.
For each i, the inner loop j loop runs N times.
So total execution time is N*c + N*N*c + c. Now ignore the
lower order terms since the lower order terms are relatively
insignificant for large input, therefore only the highest order
term is taken (without constant) which is N*N in this case.
Different notations are used to describe the limiting behavior
of a function, but since the worst case is taken so big-O
notation will be used to represent the time complexity.

Hence, the time complexity is O(N2) for the above algorithm.

Note that the time complexity is solely based on the number
of elements in array A i.e the input length, so if the length of
the array will increase the time of execution will also
increase.

Order of growth is how the time of execution depends on the

length of the input. In the above example, it is clearly evident
that the time of execution quadratically depends on the
length of the array. Order of growth will help to compute the
running time with ease.

Another Example: Let's calculate the time complexity of the

below algorithm:
count = 0
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;
This is a tricky case. In the first look, it seems like the
complexity is O(N * log N). N for the j′s loop and log(N) for i′s
loop. But it's wrong. Let's see why.
Think about how many times count++ will run.

When i = N, it will run N times.

When i = N / 2, it will run N / 2 times.
When i = N / 4, it will run N / 4 times.
And so on.
The total number of times count++ will run is N + N/2 +
N/4+...+1= 2 * N. So the time complexity will be O(N).

Some general time complexities are listed below with the

input range for which they are accepted in competitive
programming:

Input Length​ Worst Accepted Time Complexity​

Usually type of solutions

10 -12

O(N!)

Recursion and backtracking

15-18

O(2N * N)

Recursion, backtracking, and bit manipulation

18-22

O(2N * N)

Recursion, backtracking, and bit manipulation

30-40

O(2N/2 * N)​
Meet in the middle, Divide and Conquer

100
O(N4)

Dynamic programming, Constructive

400

O(N3)

Dynamic programming, Constructive

2K

O(N2* log N)

Dynamic programming, Binary Search, Sorting,

Divide and Conquer

10K

O(N2)
Dynamic programming, Graph, Trees, Constructive

1M

O(N* log N)

Sorting, Binary Search, Divide and Conquer

100M

O(N), O(log N), O(1)

Constructive, Mathematical, Greedy Algorithms

Space Complexity:
Definition -

Problem-solving using computer requires memory to hold

temporary data or final result while the program is in
execution. The amount of memory required by the algorithm
to solve given problem is called space complexity of the
algorithm.

The space complexity of an algorithm quantifies the amount

of space taken by an algorithm to run as a function of the
length of the input. Consider an example: Suppose a
problem to find the frequency of array elements.

It is the amount of memory needed for the completion of an

algorithm.

To estimate the memory requirement we need to focus on

two parts:

(1) A fixed part: It is independent of the input size. It includes

memory for instructions (code), constants, variables, etc.

(2) A variable part: It is dependent on the input size. It

includes memory for recursion stack, referenced variables,
etc.

Example : Addition of two scalar variables

Algorithm ADD SCALAR(A, B)
//Description: Perform arithmetic addition of two numbers
//Input: Two scalar variables A and B
//Output: variable C, which holds the addition of A and B
C <— A+B
return C
The addition of two scalar numbers requires one extra
memory location to hold the result. Thus the space
complexity of this algorithm is constant, hence S(n) = O(1).

The pseudo-code is as follows:

int freq[n];
int a[n];
for(int i = 0; i<n; i++)
{
cin>>a[i];
freq[a[i]]++;
}
Below is the implementation of the above approach:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count frequencies of array items
void countFreq(int arr[], int n)
{
unordered_map<int, int> freq;

// Traverse through array elements and

// count frequencies
for (int i = 0; i < n; i++)
freq[arr[i]]++;

// Traverse through map and print frequencies

for (auto x : freq)
cout << [Link] << " " << [Link] << endl;
}

// Driver Code
int main()
{
// Given array
int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 };
 int n = sizeof(arr) / sizeof(arr[0]);

// Function Call
countFreq(arr, n);
return 0;
}
Output
51
20 4
10 3
Here two arrays of length N, and variable i are used in the algorithm so, the
total space used is N * c + N * c + 1 * c = 2N * c + c, where c is a unit space
taken. For many inputs, constant c is insignificant, and it can be said that the
space complexity is O(N).
There is also auxiliary space, which is different from space complexity. The
main difference is where space complexity quantifies the total space used by
the algorithm, auxiliary space quantifies the extra space that is used in the
algorithm apart from the given input. In the above example, the auxiliary
space is the space used by the freq[] array because that is not part of the
given input. So total auxiliary space is N * c + c which is O(N) only.