Time and Space Complexity

1. Introduction to time and space complexity.
2. Different types of asymptotic notations and their limit definitions.
3. Growth of functions and types of time complexities.
4. Space and time complexity analysis of various algorithms.

1. Time and Space Complexity
Dr. Ashutosh Satapathy
Assistant Professor, Department of CSE
VR Siddhartha Engineering College
Kanuru, Vijayawada
September 25, 2022
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

2. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

3. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

4. Time and Space Complexity
Designing an efficient algorithm for a program plays a crucial role in a
large scale computer system.
Time complexityandspace complexityare the two most important
considerations for deciding the efficiency of an algorithm.
Thetime complexityof an algorithm is the number of instructions
that it needs to run to completion.
Thespace complexityof an algorithm is the amount of memory that
it needs to run to completion.
The analysis ofrunning timegenerally has received more attention
thanmemorybecause any program that uses huge amounts of
memory automatically requires a lot of time.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

5. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

6. Time Complexity
In analyzing algorithm we will not consider the following information
although they are very important.
1
The machine we are executing on.
2
The machine language instruction set.
3
The time required by each machine instruction
4
The translation, a compiler will make from the source to the machine
language.
Theexact timewe determine would no apply to many machines.
There would be the problem of thecompilerwhich could vary from
machine to machine.
It is often difficult to get reliable timing figures because ofclock
limitationsand amulti-programmingortime sharingenvironment.
We will concentrate on developing only thefrequency countfor all
statements.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

7. Time Complexity
1:x←x+ 1 ▷Frequency count is 1
1:forI←1 tondo ▷Frequency count is n+1
2:x←x+ 1; ▷Frequency count is n
3:end for
1:forI←1 tondo ▷Frequency count is n+1
2:forJ←1 tondo ▷Frequency count is n(n+1)
3: x←x+ 1; ▷Frequency count is n
2
4:end for
5:end for
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

8. Time Complexity
Algorithm 1Fibonacci sequence
1:procedureFibonacci(n)
2:if(n<0)then
3: write(”error”)
4: return
5:end if
6:if(n= 0)then
7: write0
8: return
9:end if
10:if(n= 1)then
11: write1
12: return
13:end if
14:fnm2←0
15:fnm1←1
16:forI←2to ndo
17: fn←fnm1 +fnm2
18: fnm2←fnm1
19: fnm2←fn
20:end for
21:writefn
22:end procedure
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

9. Time Complexity
Table 1.1: nin Fibonacci series
Step n<0 n = 0 n = 1 n Step n <0 n = 0 n = 1 n
1 1 1 1 1 12 0 0 1 0
2 1 1 1 1 13 0 0 0 0
3 1 0 0 0 14 0 0 0 1
4 1 0 0 0 15 0 0 0 1
5 0 0 0 0 16 0 0 0 n
6 0 1 1 1 17 0 0 0 n-1
7 0 1 0 0 18 0 0 0 n-1
8 0 1 0 0 19 0 0 0 n-1
9 0 0 0 0 20 0 0 0 n-1
10 0 0 1 1 21 0 0 0 1
11 0 0 1 0 22 0 0 0 1
Frequency Count 4 5 6 5n+4
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

10. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

11. Space Complexity
The space needed by a program is the sum of the following components.
Fixed space requirement:The component refers to space
requirement that do not depend on the number and size of the
program’sinputsandoutputs. The fixed requirements include the
instruction space(space needed to store the code), space forsimple
variables,fixed size structured variable and constants.
Variable space requirement:This component consists of the space
needed by structured variables whosesizedepends on the particular
instance i, of the problem being solved. It also includes the
additional spacerequired when a function usesrecursion.
The space requirementS(P)of an algorithm P may therefore be written
asS(P) = c + SP, wherecandSPare theconstantandinstance
characteristics, respectively. First, we need to determine which instance
characteristics to use for a give problem to reduce the space requirements.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

12. Space Complexity
Algorithm 2Square of the given Number
1:proceduregetsquare(n)
2:returnn*n
3:end procedure
We can solve the problem without consuming any extra space, hence the
space complexity is constant.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

13. Space Complexity
Algorithm 3Sum of array elements
1:procedurecalculatesum(A,n)
2:sum←0
3:fori←0 ton−1do
4: sum←sum+A[i]
5:end for
6:end procedure
n,sumand i take constant sum of3 units, but the variableAis an array,
it’sspaceconsumptionincreaseswith the increase of input sizen.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

14. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

15. Basics
The main idea of asymptotic analysis is to have a measure of
efficiency of algorithmsthat doesn’t depend onmachine specific
constants.
Asymptotic analysisof an algorithm refers to defining the
mathematical boundation/framingof its run-time performance.
It doesn’t require algorithms to be implemented and time taken by
programs to be compared.
Asymptotic notations are mathematical tools to representtime
complexityof algorithms forasymptotic analysis.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

16. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

17. Asymptote
A’Line’that continually approaches a givencurvebut does not meet
it at anyfinite distance.
The termasymptoticmeans approaching a value or curve arbitrarily
closely (i.e., as some sort of limit is taken).
A line or a curve A that isasymptoticto given curve C is called the
asymptoteof C.
Figure 2.1:
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

18. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

19. O (Big-Oh) notation
Big-Ohis used as a tight upper-bound on the growth of an
algorithm’s effort (this effort is described by the function f(n)).
Letf(n)andg(n)be functions that map positive integers to positive
real numbers. We say thatf(n)isO(g(n))orf(n)∈O(g(n)), if
there exists a real constantc>0and there exists an integer constant
n0≥1such thatf(n)≤cg(n)for every integern≥n0.
In other wordsO(g(n))={f(n): there exist positive constantscand
n0such that0≤f(n)≤cg(n)for alln≥n0}
Figure 2.2: ∈O(g(n))
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

20. O (Big-Oh) notation
Question 1:Consider the function f(n) = 6n+ 135. Clearly. f(n) is
non-negative for all integers n≥0. We wish to show that f(n)=O(n
2
).
According to the Big-oh definition, in order to show this we need to find
an integer n0, and a constant c>0 such that for all integers, n≥n0, f(n)
= c(n
2
)
Answer:Suppose we choose c = 1, and f(n) = cn
2
.
⇒6n+135 = cn
2
= n
2
[Since c = 1] n
2
-6n-135 = 0
⇒(n-15)(n+9) = 0
Since (n+9)>0 for all values n≥0, we conclude that (n-15) = 0
⇒n0= 15 for c = 1
For c = 2, n0= (6 +
√
1116)/4≈9.9
For c = 4, n0= (6 +
√
2196)/8≈6.7
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

21. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

22. Ω (Big-Omega) notation
Big-Omega (Ω)is the tight lower bound notation.
Letf(n)andg(n)be functions that map positive integers to positive
real numbers. We say thatf(n)is Ω(g(n))orf(n)∈Ω(g(n))if
there exists a real constantc>0and there exists an integer constant
n0≥1such thatf(n)≥cg(n)for every integern≥n0.
In other words Ω(g(n))={f(n): there exist positive constantscand
n0such that0≤cg(n)≤f(n)for alln≥n0}.
Figure 2.3: ∈Ω(g(n))
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

23. Ω (Big-Omega) notation
Question 2:Consider the function f(n)= 3n
2
-24n+72. Clearly f(n) is
non-negative for all integers n≥0. We wish to show that f(n) = Ω(n
2
).
According to the big-omega definition, in order to show this we need to
find an integer n0,and a constant c>0 such that for all integers n = n0,
f(n) = cn
2
.
Answer:Suppose we choosc c = 1, Then f(n) = cn
2
⇒3n
2
-24n+72 = n
2
⇒2n
2
-24n+72 = 0
⇒2(n-6)
2
= 0
Since (n-6)
2
= 0, we conclude that n0= 6.
So we have that for c = 1 and n≥6, f(n) = cn
2
. Hence f(n) = Ω(n
2
).
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

24. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

25. o (Little-Oh) notation
Little-oh (o)is used as a loose upper-bound on the growth of an
algorithm’s effort (this effort is described by the functionf(n)).
Letf(n)andg(n)be functions that map positive integers to positive
real numbers. We say thatf(n)iso(g(n))orf(n)∈o(g(n))if for
any real constantc>0, there exists an integer constant n0≥1such
thatf(n)<cg(n)for every integern≥n0.
In other wordso(g(n))={f(n): there exist positive constantscand
n0such that0≤f(n)<cg(n)for alln≥n0}.
Figure 2.4: ∈o(g(n))
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

26. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

27. ω(Little-Omega) notation
Little Omega (ω)is used as a loose lower-bound on the growth of
an algorithm’s effort (this effort is described by the functionf(n)).
Letf(n)andg(n)be functions that map positive integers to positive
real numbers. We say thatf(n)isω(g(n))orf(n)∈ω(g(n))if for
any real constantc>0, there exists an integer constant n0≥1such
thatf(n)>cg(n)for every integern≥n0.
In other wordsω(g(n))={f(n): there exist positive constantscand
n0such that0≤cg(n)<f(n)for alln≥n0}.
Figure 2.5: ∈ω(g(n))
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

28. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

29. θ(Theta) notation
Letf(n)andg(n)be functions that map positive integers to positive
real numbers. We say thatf(n)isθ(g(n))orf(n)∈θ(g(n))if and
only iff(n)∈O(g(n))andf(n)∈Ω(g(n))
θ(g(n))={f(n): there exist positive constantsc1,c2andn0such
that0≤c1g(n)≤f(n)≤c2g(n)for alln≥n0}
Figure 2.6: ∈θ(g(n))
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

30. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

31. Limit Definition
1
if f(n)∈O(g(n))thenlimn→∞
f(n)
g(n)
∈[0,∞)
2
if f(n)∈o(g(n))thenlimn→∞
f(n)
g(n)
= 0
3
if f(n)∈Ω(g(n))thenlimn→∞
f(n)
g(n)
∈(0,∞]
4
if f(n)∈ω(g(n))thenlimn→∞
f(n)
g(n)
=∞
5
if f(n)∈θ(g(n))thenlimn→∞
f(n)
g(n)
∈(0,∞)
Examples
1.n
2
−2n+ 5∈O(n
3
)⇔limn→∞
n
2
−2n+5
n
3= limn→∞
1
n
−
2
n
2+
5
n
3= 0
2.n
2
+ 1∈Ω(n)⇔limn→∞
n
2
+1
n
=∞
3.n
2
+ 3n+ 4∈θ(n
2
)⇔limn→∞
n
2
+3n+4
n
2= limn→∞(1 +
3
n
+
4
n
2) = 1
4.7n+ 8∈o(n
2
)⇔limn→∞
7n+8
n
2= limn→∞(
7
n
+
8
n
2) = 0
5.4n+ 6∈ω(1)⇔limn→∞
4n+6
1
=∞
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

32. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

33. Growth of Functions
The order ofgrowth of the running timeof an algorithm gives a
simple characterization of the algorithm’s efficiency and also allows us
to compare the relative performance of alternative algorithms.
We are concerned with how the running time of an algorithm
increases with the size of the input increases.
We writeO(1)to mean a computing time which is aconstant.O(n)
is calledlinear,O(n
2
)is calledquadratic,O(n
3
)is calledcubicand
O(2
n
)is calledexponential.
If an algorithm takes timeO(log2n)it is faster, for sufficiently large
n, than if it had takenO(n). Similarly,O(nlog2n)is better than
O(n
2
)but not as good asO(n).
It we have two algorithms which perform the same task, and the first
has a computing time, which isO(n)and the secondO(n
2
), then we
will usually take the first as superior.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

34. Growth of Functions
Table 3.1:
n 10n n
2
/2
1 10 0.5
5 50 12.5
10 100 50
15 150 112.5
20 200 200
25 250 312.5
30 300 450
Forn≤20, algorithm two had a smaller computing time, but once past
that point, algorithm one became better. This shows why we chose the
algorithm with the smaller order of magnitude.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

35. Growth of Functions
For a given algorithm, the total frequency count of each statement
represented by a polynomial is as follows:
f(n) =ckn
k
+ck−1n
k−1
+...+c1n
1
+c0
Wherecis are constants,c̸=0andnis a parameter. Using big-oh
notation,f(n)= O(n
k
).
On the other hand, if any step is executed in2
n
times or more, then
the expression is
f(n) =m2
n
+ckn
k
+ck−1n
k−1
+...+c1n
1
+c0
Wheremandcis are constants,c̸=0andnis a parameter. Using
big-oh notation,f(n)= O(2
n
).
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

36. Growth of Functions
Table 3.2:
log2nnnlog2nn
2
n
3
2
n
n!
0 1 0 1 1 2 1
1 2 2 4 8 4 2
2 4 8 16 64 16 24
3 8 24 64 512 256 40,320
4 16 64 2564096 65,536 20,922,789,888,000
5 32 160 1024327682,147,483,6482.631308369E+35
Another valid performance measure of an algorithm isspace. Often, one
cantrade spacefortime, getting a faster algorithm while using more
space.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

37. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

38. Types of Time Complexities
Time complexityusually depends on thesize of the algorithmand
input.
Thebest-casetime complexity of an algorithm is a measure of the
minimum time that the algorithm will require for an input of size n.
Theworst-casetime complexity of an algorithm is a measure of the
maximum time that the algorithm will require for an input of size n.
After knowing theworst-casetime complexity, we can guarantee that
the algorithm willnever take more than this time.
The time that an algorithm will require to execute a typical input
data of size n is known asaverage-casetime complexity.
We can say that the value that is obtained byaveraging the running
timeof an algorithm forall possible inputs of size ncan determine
average-case time complexity.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

39. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

40. Rules for Complexity Analysis
Rule 1: Sequence
The worst case running time of a sequence of C statements such as
statement 1;
statement 2;
statement 3;
.
.
.
statement m;
is O(max(T1(n), T2(n), ...Tm(n))), where running time of Si, the i
th
statement in the sequence, is O(Ti(n))
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

41. Rules for Complexity Analysis
Rule 2: Iteration
The worst case running time of a C for loop such as
for(statement 1; statement 2; statement 3)
statement 4
is O(max(T1(n), T2(n)(I(n)+1), T3(n)I(n), T4(n)I(n))), where the
running time of statement Siis O(Ti(n)), for i=1,2,3 and 4, and I(n) is
the number of iterations executed in the worst case.
Rule 2: Selection
The worst care running time of a C if- else such as
if(statement 1) statement 2;
elsestatement 3;
is O(max(T1(n), T2(n), T3(n))), where the running time of statement Si,
is O(Ti(n)), for i= 1,2 and 3.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

42. Rules for Complexity Analysis
Algorithm 4Prefix-sum
1:procedureprefix-sum(A,n)
2:fori←n−1 to 0do
3: sum←0
4: forj←0 toido
5: sum←sum+A[j]
6: end for
7: A[i]←sum
8:end for
9:end procedure
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

43. Rules for Complexity Analysis
Table 3.3:
Statement Frequency Count Time
1 1 O(1)
2 n+1 O(n)
3 n O(n)
4 (n+1) + n + ....+ 2 O(n
2
)
5 n + (n-1) + ...+ 1 O(n
2
)
6 n + (n-1) + ...+ 1 O(n
2
)
7 n O(n)
8 n O(n)
9 1 O(1)
f(n) (n+1)(n+2)/2 + n(n+1) + 4n + 2 O(n
2
)
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

44. Outline
1
Algorithm Analysis
Time and Space Complexity
Time Complexity
Space Complexity
2
Asymptotic Notation
Basics
Asymptote
Big-Oh notation
Big Omega notation
Little-Oh notation
Little-Omega notation
Theta notation
Limit Definition
3
Complexity Analysis
Growth of Functions
Types of Time Complexities
Time Complexity Analysis
Space Complexity Analysis
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

45. Space Complexity Analysis
Example 1
InAlgorithm 2, the variablenoccupies a constant4 Bytesof
memory. Thefunction callandreturn statementcome under the
auxiliary space and let’s assume4 Bytesall together.
The total space complexity is8 Bytes.Algorithm 2has a space
complexity ofO(1).
Example 2
InAlgorithm 3, the variablesn,sum, andioccupy a constant12
Bytesof memory. Thefunction call,initialisationof the for loop
andwrite functionall come under the auxiliary space and let’s
assume4 Bytesall together.
The total space complexity is4n + 16 Bytes.Algorithm 3has a
space complexity ofO(n).
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

46. Space Complexity Analysis
Algorithm 5Factorial of a number
1:procedurefactorial(n)
2:fact←1
3:fori←1 tondo
4: fact←fact+i
5:end for
6:returnfact
7:end procedure
The variablesn,fact, andioccupy a constant12 Bytesof memory. The
function call,initializingthe for loop andreturn statementall come
under the auxiliary space and let’s assume4 Bytesall together.
The total space complexity is16 Bytes.Algorithm 5has a space
complexity ofO(1).
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

47. Space Complexity Analysis
Algorithm 6Recursive: Factorial of a number
1:procedurefactorial(n)
2:if(n≤1)then
3: return1
4:else
5: returnn∗FACTORIAL(n−1)
6:end if
7:end procedure
The variablenoccupies a constant4 Bytesof memory. Thefunction
call,ifandelseconditions andreturn statementall come under the
auxiliary space and let’s assume4 Bytesall together.
The total space complexity is4n+4 Bytes.Algorithm 6has a space
complexity ofO(n).
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

48. Space Complexity Analysis
Algorithm 7Summation of two numbers
1:procedureaddition(a,b)
2:c←a+b
3:writec
4:end procedure
The variablesa,bandcoccupy a constant12 Bytesof memory. The
function call,ifandelseconditions andwrite functionall come under
the auxiliary space and let’s assume4 Bytesall together.
The total space complexity is16 Bytes.Algorithm 7has a space
complexity ofO(1).
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

49. Summary
Here, we have discussed
Introduction to time and space complexity.
Different types of asymptotic notations and their limit definitions.
Growth of functions and types of time complexities.
Time and space complexity analysis of various algorithms.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022

50. For Further Reading
H. Sahni and A. Freed.
Fundamentals of Data Structures in C (2
nd
edition).
Universities Press, 2008.
A. K. Rath and A. K. Jagadev.
Data Structures Using C (2
nd
edition).
Scitech Publications, 2011.
Dr. Ashutosh Satapathy Time and Space Complexity September 25, 2022