DURGASOFT
O(1), O(n), O(n2), O(n3), O(logn), O(nlogn) etc
Asymptotic Notations:
~~~~~~~~~~~~~~~~~~~~~
it is used to measure/represent time and space complexity of any algorithm.
1. Big-Oh ----> O
2. Omega ----> W
3. Theta -----> theta
4. Little oh -> o
5. Little omega --> w little omega
Big "Oh" (O):-
~~~~~~~~~~~~~~
a function f(n) is said to be in O(g(n)) denoted by f(n)=O(g(n)) is bounded above by
some constant multiple of g(n) for all n, i.e. there exist positive constant 'c' and non-
negative integer 'n0' such that f(n)<=c*g(n) for every n>=n0.
diagram
Ex:
f(n) = 2n+2
g(n) = n^2
where n>=3
Omega Notation (W):-
~~~~~~~~~~~~~~~~~~~~
a function f(n) is said to be in W(g(n)) denoted by f(n)=W(g(n)) is bounded below by
some constant multiple of g(n) for all n, i.e. there exist positive constant 'c' and non-
negative integer 'n0' such that f(n)>=c*g(n) for every n>=n0.
diagram
Ex:
f(n) = 2n^2 + 3
g(n) = 7n
where n0>=3
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
41 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Theta notation (0):-
~~~~~~~~~~~~~~~~~~~~
a function f(n) is said to be in 0(g(n)) denoted by f(n)=0(g(n)) is bounded with above
and below by some constant multiples of g(n) for all n, i.e. there exist positive
constant 'c1' and 'c2' and non-negative integer 'n0' such that c1*g(n)<=f(n)<=c2*g(n)
for every n>=n0.
digram
Ex:
f(n) = 4n+1
g(n) = n , c1=4 and c2 = 5
where n>=1
algorithm-sample algorithms
flow chart
implementing problems in java
analysis of algorithms
space complexity
time complexity
performance measurements (notations)
5pm ---> 7pm
------------
algorithm-sample algorithms
flow chart
implementing problems in java
pending
-------
analysis of algorithms
space complexity
time complexity
performance measurements (notations)
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
42 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Recursion:
----------
01) Introduction to functions
02) Why Recursion?
03) Recursion
04) Base condition
05) Finate and Infinate Recursion
06) Mathematical Interpretation of Recursion
07) Properties of Recursion
08) Advantages & disadvantages of recursion
09) Difference between iteration and recursion
10) Implement a program to print natural numbers from 1 to n
11) Implement a program to calculate sum of 'n' natural numbers
12) Implement a program to calculate a^b (a to the power b)
13) Implement a program to find factorial of the given number?
14) Implement a program to calculate product of two integer values (a*b)
15) Implement a program to check whether the given number is prime number or
not?
16) Implement a program to find sum of digits present in the given number?
17) Implement a program to calcualte reverse of the given number?
18) Implement a program to count number of digits present in the given number?
19) Implement a program to convert decimal number into binary?
20) Implement a program to find nth fib number
21) Implement a program to find LCM of two numbers?
22) Implement a program to find HCF/GCD of the given two numbers
23) Implement a program to find reverse of the given string using recursion?
24) Implement a program to remove the given character from a string?
25) Implement a program to return Str, where all the adjacent chars are sep by a "*".
26) Implement a program to return new string where identical adjcent chars are sep
by *
27) Implement a program to return true if a string nesting of zero or more pairs of ()
28) Implement a program to count number of times, the give char occurred.
29) IMP to replace the given old character with new character in the original string?
30) IMP to count the number of times given string appeared in the original string?
31) IMP to replace the given string with new string?
32) Towers of Hanoi
Recursion:-
~~~~~~~~~~~
==> function: set of instructions or sequence of operations under a common name or
block
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
43 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Ex:
fun()
{
--------------
--------------
--------------
}
we can call this fun any number of times based on our requirement.
advantage: ----> code reusability
Ex:
int add(int a,int b){
return a+b;
}
Ex:
boolean insertRecordInToMysqlDatabase(String name, int htno, double
percentage){
-----------------------
-----------------------
-----------------------
-----------------------
}
[Link](insertRecordInToMysqlDatabase("AAA",111,67.89));
[Link](insertRecordInToMysqlDatabase("BBB",222,77.89));
[Link](insertRecordInToMysqlDatabase("CCC",333,87.89));
[Link](insertRecordInToMysqlDatabase("DDD",444,97.89));
4+4+4+4=16
4+4=8
C/C++/Python ======> functions
Java/Python =======> methods
Ex:
class Demo
{
boolean insertRecordInToMysqlDatabase(String name, int htno, double
percentage){
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
44 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
-----------------------
-----------------------
-----------------------
-----------------------
}
}
Demo obj = new Demo();
[Link]([Link]("AAA",111,67.89));
[Link]([Link]("BBB",222,77.89));
[Link]([Link]("CCC",333,87.89));
[Link]([Link]("DDD",444,97.89));
Q) can we declare a function within another function or not?
------------------------------------------------------------
Yes, we can define, but only few programming languages are supporting this.
C -----> Yes
C++ ---> Yes
Java --> No
we can use a function within another function, we can't declare a definition of a
function within another function/method.
Ex:
void method1(){
------------------
------------------
void method2(){
-------------------
-------------------
}
-------------------
-------------------
}
Ex:
void method1(){
------------------
------------------
method2();
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
45 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
-------------------
-------------------
}
Ex:
void method1(){
------------------
------------------
[Link](10,20);
-------------------
-------------------
}
Recursion is a process of calling a method/function by itself, in this process the
method which is invoked is called as 'Recursive Method'.
this recursion is divided into two ways based on method calls...
1) infinate recursion
2) finate recursion
infinate recursion:
-------------------
the method which called by itself, infinate times. we will get Error message 'Stack
Over Flow' error we will get.
Ex:
import [Link].*;
class Demo{
void m(){
[Link]("Good Evening");
m();
}
}
class Test
{
public static void main(String[] args)
{
Scanner obj = new Scanner([Link]);
Demo d = new Demo();
d.m();
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
46 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
}
output:
-------
Good Evening
Good Evening
Good Evening
Good Evening
.
.
.
Exception in thread "main" [Link].
finate recursion:-
------------------
a method which is called by itself, and terminates at finate number of steps is called
as finate recursion.
we can make this finate recursion based on 'BASE CONDITION'.
base condition:
---------------
It is a special, we have to create inside recursive calls so that our recursion should
terminate at a finate steps.
import [Link].*;
class Demo{
static int c;
void m(){
if(c>10)
return;
else
{
[Link]("Good Evening, c="+c);
c++;
m();
}
}
}
class Test
{
public static void main(String[] args)
{
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
47 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Scanner obj = new Scanner([Link]);
Demo d = new Demo();
d.m();
}
}
output:
-------
C:\prakashclasses>javac [Link]
C:\prakashclasses>java Test
Good Evening, c=0
Good Evening, c=1
Good Evening, c=2
Good Evening, c=3
Good Evening, c=4
Good Evening, c=5
Good Evening, c=6
Good Evening, c=7
Good Evening, c=8
Good Evening, c=9
Good Evening, c=10
Why we need Recursion:
~~~~~~~~~~~~~~~~~~~~~~
some tims, if we got a problem, we need to divide that big problems, into small small
units, and find solutions for these sub-problems, which inturn creates solution for that
bigger problem. This is the senario major applications are using. Ex: Recusrion, DAC...
Mathematical Interpretation of Recursion:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Ex: Sum of 'n' natural numbers
In Math:
f(n) = 1 + 2 + 3 + 4 + 5 + ...... + n
In Recursion:
f(n) = 1 , n=1
f(n) = n + f(n-1), n>1
f(5) = n + f(n-1) = 5 + f(4)
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
48 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
f(4) = n + f(n-1) = 4 + f(3)
f(3) = n + f(n-1) = 3 + f(2)
f(2) = n + f(n-1) = 2 + f(1)
f(1) = 1
stack ===> 5, 4, 3, 2 , 1
1+2=3+3=6+4=10+5=15
Properties of Recursion:
~~~~~~~~~~~~~~~~~~~~~~~~
1) same operations with multiple inputs.
2) we will divide the entire problem into small problems.
3) base condition is very very important in recursion, else it leads to infinate exe.
advantages of recursion:
~~~~~~~~~~~~~~~~~~~~~~~~
1) recursive algorithms are easier to write.
2) easy to solve natural big problems, Ex: Towers of Hanoi problem
3) reduce unnecessary function calls.
4) reduce length of the code.
5) very useful while solving data structure related problems.
6) we can evaulate some expressions, infix, prefix and postfix etc
disadvanatges of recursion:
~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) recursion uses extra stack space.
2) redundent computations
3) tracing will be difficult
4) slower in execution
5) runs out of memory (StackOverFlow Error)
sir what i remember is .....
java has garbage collectors which clears memory after execution.
......
so why we need to worry about space complexity at all
difference between recursion and iteration?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
49 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
Recursion:
----------
1) terminates when base condition is true.
2) functions concept.
3) extra space is required.
4) smaller code.
Iteration:
----------
1) terminates when condition is false.
2) looping statement concepts.
3) extra space is not required.
4) bigger code.
01. Implement a program to print natural numbers from 1 to n
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import [Link].*;
class Demo
{
static void print(int n){
if(n>=1)
{
//[Link](n+" "); ===> n, n-1, n-2, ... 1
print(n-1);
[Link](n+" "); // ==> 1, 2, 3, 4, .... n
}
}
}
class Test
{
public static void main(String[] args)
{
Scanner obj = new Scanner([Link]);
int n = [Link]();
[Link](n);
}
}
output:
-------
C:\prakashclasses>javac [Link]
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
50 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]