DURGASOFT
else
return n*fact(n-1);
}
space complexicity ------>
f(n) = 1 + 1
f(n-1) = 1 + 1
f(n-2) = 1 + 1
.
.
f(n-(n-1)) = 1 + 1
f(n-n) = 1
--------------------
sp(fact) = 2n+1 units
---------------------
Ex: space complexity for prime number or not application using recursion
--------------------------------------------------------------------------
algorithm isprime(n,i)
{
if(i==1)
return true;
else if(n%i==0)
return false;
else
return isprime(n,--i);
}
sp(isprime) ----->
isprime(n) -----> 2
isprime(n-1) -----> 2
isprime(n-2) -----> 2
isprime(n-3) -----> 2
isprime(n-n) -----> 1 or 1
---------------------------
sp(isprime) = 2n+1
---------------------------
time complexity:
----------------
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
31 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
the time complexity of an algorithm is the amount of computer time it needs to
complete the task.
tc(p) = compile time + execution time
= execution time (ignore compile time, compilation will be done only one time)
step count method to calculate time complexity
----------------------------------------------
1) for algorithm heading ------> 0
2) for braces -----------------> 0
3) for expressions ------------> 1
4) for if conditions ----------> 1
5) for loops ------------------> based on number of iterations 'n'
java code for sorting ----> 10 lines
py code ------------------> 1 line [Link]()
Ex: addition of three numbers
------------------------------
1: algorithm addition(a,b,c)
2: {
3: return a+b+c;
4: }
1 -----> 0
2 -----> 0
3 -----> 1 unit
4 -----> 0
tc(addition) = 1 unit
case1:
algorithm addition(a,b,c)
{
int d = a+b+c;
return d;
}
case2:
algorithm addition(a,b,c)
{
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
32 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
return a+b+c;
}
Ex: find max of two numbers
---------------------------
1: algorithm max(a,b)
2: {
3: return (a>b)?a:b;
4: }
1 -----> 0
2 -----> 0
3 -----> 1 unit
4 -----> 0
tc(addition) = 1 unit
Ex: find max of two numbers
---------------------------
1: algorithm max(a,b)
2: {
3: if(a>b)
4: return a;
5: else
6: return b;
7: }
1 -----> 0
2 -----> 0
3 -----> 1 unit
4 -----> 0
5 -----> 0
6 -----> 0
7 -----> 0
tc(addition) = 1 unit
Ex: find max of three numbers
---------------------------
1: algorithm max(a,b,c)
2: {
3: if(a>b && a>c)
4: return a;
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
33 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
5: else if(b>a && b>c)
6: return b;
7: else
8: return c;
9: }
1 -----> 0
2 -----> 0
3 -----> 1 unit
4 -----> 0
5 -----> 1 unit
6 -----> 0
7 -----> 0
8 -----> 0
9 -----> 0
tc(addition) = 2 unit
Note: &&, || operators are also called shortcircuit operators
cond1 && cond2 && cond3 && cond4 && cond5 ---> if first cond is false, then stop
exe
cond1 || cond2 || cond3 || cond4 || cond5 ---> if first cond is true, continue
SUCH BEUTIFUL NATURE THEY HAVE DESIGNED AT LANGUAGE LEVEL
Ex: sum of 'n' natural numbers
------------------------------
1: algorithm sum(n)
2: {
3: sum=0;
4: for(i=1;i<=n;i++)
5: {
6: sum=sum+i;
7: }
8: return sum;
9: }
1 ------> 0
2 ------> 0
3 ------> 0
4 ------> n+1 ['n' times true '1' time false]
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
34 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
5 ------> 0
6 ------> n
7 ------> 0
8 ------> 0
9 ------> 0
tc(sum) = n+1+n = 2n+1
Ex: sum of 'n' even numbers
----------------------------
1: algorithm sum(n)
2: {
3: sum=0;
4: for(i=1;i<=n;i++)
5: {
6: if(i%2==0)
7: sum=sum+i;
8: }
9: return sum;
10: }
1------> 0
2------> 0
3------> 0
4 -----> n+1
5 -----> 0
6 -----> n
7 -----> n/2
8 -----> 0
9 -----> 0
10 ----> 0
tc(sum) = n/2+2n+1
Ex: find max element present in an array
----------------------------------------
1. algorithm maxElement(a,n)
2. {
3. max = a[0];
4. for(i=1;i<n;i++)
5. {
6. if(max<a[i])
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
35 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
7. {
8. max = a[i];
9. }
10. }
11. return max;
12. }
1-----> 0
2 ----> 0
3 ----> 0
4 ----> n+1-1 = n [1 comp we are not considering first element]
5 ----> 0
6 ----> n-1
7 ----> 0
8 ----> n-1
9 ----> 0
10 ---> 0
11 ---> 0
12 ---> 0
tc(maxElement) = n+n-1+n-1=3n-2
O(n)
Ex1: sorting of an array
------------------------
algorithm sort(a,n)
{
for(i=0;i<n;i++) ---------> n+1
{
for(j=i+1;j<n;j++) ---> n*(n) ---> n^2
{
if(a[i]>a[j]) ----> n^2 - 1
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
36 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
ts(sort) -----> n+1+n2+n2-1 ----> 2n^2+n
if data is already in sorting ASC ----> x
if data is already in sorting DESC ---> x
if data is not in sorting --------> x
Ex2: sum of two matrices
------------------------
algorithm(a,b,n,n)
{
for(i=0;i<n;i++) --------> n+1
{
for(j=0;j<n;j++) ----> n*(n+1) ---> n^2 + n
{
c[i][j] = a[i][j] + b[i][j]; ---> n^2
}
}
}
tc(sum of two mat) = n+1+n2+n+n2 ---> 2n^2 + 2n + 1 ---> O(n2)
Sir please explain time complexity of following cases
for(i=1;i<=n;i++) ----> n+1
Case 1
for(int i=0; i<=n; i++) -----> n+1+1 ---> n+2
Case 2
for(int i=0; i<n; i++) ------> n+1-1+1 -> n+1
Case 3
for(int i=1; i<=n; i++) ------> n+1
Case 4
for(int i=1; i<n; i++) -------> n+1-1 ---> n
Ex: Matrix Multiplication
-------------------------
for(i=0;i<n;i++) -------------------------------------> n+1+1-1===> n+1
{
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
37 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
for(j=0;j<n;j++) ---------------------------------> n*(n+1+1-1) ==> n*(n+1) = n^2+n
{
c[i][j] = 0; ---------------------------------> n*(n) = n^2
for(k=0;k<n;k++) -----------------------------> n^2 * (n+1-1+1) ==> n^2*(n+1)
{
c[i][j] = c[i][j] + (a[i][k] * b[k][j]); --> n^2 * (n) ===> n^2*n=n^3
}
}
}
tc(mm) = n+1 + n^2+n + n^2 + n^3 + n^2 + n^3
= 2n3 + 3n2 + 2n + 1
O(n3)
space and time complexity of any algorithm
algorithm cases ----> best case, avg case, worst case
asymptotic notations --> 5 notations
introduction to algorithms
introduction to data structures
applications of data structures
steps to prepare algorithm
steps to prepare flowchart
steps to implement a program in java
sample programs (10 programs)
analysis of algorithms
space complexity calculation
time complexity calculation
best case, worst case and average case analysis
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
best case:
----------
if we are looking for a sol, which is avaialble at very first location, then such type of
case is called as best case.
Ex:
11, 12, 13, 14, 15, 16
key = 11
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
38 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
comp ---> 1st comp ---> best case
worst case:
-----------
if we are looking for a data, which is available at last position or may not be
available, then such type of cases are called as worst case.
Ex:
11, 12, 13, 14, 15, 16
key = 16
comp ---> 6, success
key = 17
comp ---> 6, failure
average case:
-------------
if we are looking for multiple data's, the time/space taken for that alg is calcualted
based on sum of the possible case.
Ex:
11, 12, 13, 14, 15, 16
key=11 ----> 1
key=12 ----> 2
key=13 ----> 3
key=14 ----> 4
key=15 ----> 5
key=16 ----> 6
key=17 ----> 6
avg case ===> total comp/[Link] cases
Note: we can ignore this case.
Real time example:
------------------
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
39 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
i have given Rs. 10,000/- to my friend....
1st of everymonth -----> 50,000/-
15th of everymonth ----> 5000/-
30th of everymonth ----> 1000/-
1) 1st nov 2022 ----> Happy ----> Best case
2) 14th nov 2022 ---> Good -----> Average case
3) 16th nov 2022 ---> Good -----> Average case
4) end of the month-> Good -----> Worst case
Note: we can ignore this average case.
best case ------> 1 unit (constant value) ----> O(1)
average case ---> n units ------n-2--------------> O(n)
worst case ------> n units -----n--------------> O(n)
Ex: find max element present in an array
----------------------------------------
1. algorithm maxElement(a,n)
2. {
3. max = a[0];
4. for(i=1;i<n;i++)
5. {
6. if(max<a[i])
7. {
8. max = a[i];
9. }
10. }
11. return max;
12. }
11, 10, 9, 8, 7, 6 ----> max: 11
Hence, we will calcualte time and space complexity based on only WORST CASE
COMP.
O(----)
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
40 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]