1-ADA.Intro

Download as pdf or txt
Download as pdf or txt
You are on page 1of 31

ALGORITHM

¢ It is a combination* of Sequence ** of finite


steps*** to solve a particular problem.
¢ Combination means all steps are compulsory.
No step is unnecessary.
¢ Sequence means order is important.
¢ Steps should be finite.
EXAMPLE!!
Addition of two nos ()
{
1. Take two nos a and b.
2. Add a && b and store in c.
3. Return c.
}
¢ Algorithm is a well defined procedure
which will take a set of values as input and
which will produce a set of values as
output.
PROPERTIES OF ALGORITHM
1. Input :- Zero or more input(finite).
2. Output :- At least one output(finite).
3. It should produce the output within the finite
time.
4. It should be deterministic in nature. Every
steps is unambiguous.
5. Simplicity :- Every step in algorithm should
perform at least one task.
6. It should be independent from the
programming language.
STEPS TO CONSTRUCT ALGORITHMS
1. Problem definition :- What will be the i/p &
o/p.
2. Constraint or condition must be satisfied.
3. Design the algorithm.
4. Draw flow chart.
5. Validation (testing).
6. Implementation.
7. Analysis.
ALGORITHM!DESIGN TECHNIQUES
1. Divide & Conquer
2. Greedy
3. Dynamic Programming
4. Backtracking
ANALYSIS OF AN ALGORITHM
¢ For example sorting N no’s has so many
algorithms like bubble sort or Insertion sort.
¢ Now all algorithms produce same output. So
which algorithm is better is decided by
analysis.
¢ BS,QS.MS,SS,IS,HS
¢ First we compare the time then space.
¢ Here QS, MS & HS take the same time
complexity so will go for space.
¢ As QS take least space so overall QS is better.
COMPLEXITY!ANALYSIS
¢ For a problem P if A is a algorithm then time
requirement for A i.e.
¢ T(A) = Compile time for A+ Run time for A.

Compiler(S/W) CPU(H/W)
¢ Compile time depends on the programming
language used to write the program.
¢ Run time is dependent on the type of process
used.
APOSTIARY!&!APRIORI!ANALYSIS!!
¢ If we know the programming language &
type of processor & we give the time
complexity then it is Apostiary analysis .It
is also called dependent analysis. Exact
analysis.
¢ If we give the analysis independent of
programming language & Processor then
it is Apriori analysis. It is also called
independent analysis. Approximate
analysis
APRIORY!ANALYSIS
¢ It is a determination of order of magnitude of a
statement. It means how many times the
statement will execute. For example:-
main()
{
x= y + z ;.......................(i)
}
Order of magnitude of this statement is 1 so
the time complexity is O(1) or order(1).
Example 2:-
main()
{
x= y + z;...................................(i) 1
for( i=1; i<=n ; i++)
{
a= b + c;........................(ii) n
}
}
¢ Order is 1+n when n !, smaller terms can
be neglected. So order is O(n).
Example 3:-
main()
{ x=y+z; .............. (i) 1
for(i=1; i<=n; i++)
{
a=b+c; .................(ii) n
}
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{
x1=y1+z1; ...................(iii) n2
} } }
Order of magnitude is 1+n+n2 i.e. O(n2 ).
Example 4:-
main()
{for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{
x=y+z; ..............(i) n2
a=b+c; ..............(ii) n2
} }}
Order of magnitude is n2+n2 = 2 n2
when n ! 2 does not count i.e. O(n2 ).
¢ In the previous computation for loop statement
are also actually counted. In the statement
for (i=1 ; i<=n; i++)
{..........
}
¢ i=1 executed once. i<=n is tested n+1 times i.e.
N times for true conditions & once tested for
false condition to come out of the loop.
¢ i++ is executed n times and body is executed n
times.
¢ So major factor contributing is n. So we directly
say that for loop executed for n times.
Q.1:-Find the time complexity for the following
C program:-
main()
{ i=n;
while(i>=1)
{
i=i/2;
}
}
¢ First consider the code without the equal sign of while
i.e. While(i>1)
¢ Take some arbitrary value of n say 4. The major factor
for this code is the while loop.
¢ First the while condition is tested with i=4. while
(4>1) is a true condition , so the body of loop is
visited.
¢ The value of i becomes i/2 i.e. 4/2=2 & again the while
loop condition is tested . While (2>1) is a true
condition so body is again visited. Now i becomes i/2
i.e. 2/2=1 & now again test condition is tested. While
(1>1) is a false condition , so control comes out of this
loop.
¢ So for n=4, while loop body is visited 2 times.
Similarly for n=8, body will be visited 3 times.
N=2 N=4 N=8
main()
{
1 times 2 3 times
i=n; times
while(i>=1)
{ N=32 N=N

i=i/2;
} 6 times Log n Finally
} times considering >
= both then
Lon n + 1
times
Que.2:-

main()
{
i=n; \\n>1
while(i<=1)
{
i=i/2;
x=y+z;
}
}
Que.2:-
¢ Only (i) statement is
main()
executed so order of
complexity is O(n).
{
¢ The condition of while
i=n; \\n>1....(i)
while(i<=1) loop always becomes
{
false.
i=i/2; ........(ii)
x=y+z; .......(iii)
}
}
Q.3:-
main()
{x=y+z;
for(i=1;i<=n;i++)
{ a=b+c;
}
for(i=1;i<=n;i++)
{

for(j=1;j<=n/2;j++)
{ x1=y1+z1;
} } }
Q.3 Order of magnitude of
main()
{ x=y+z; Line 3= n2
Line 2 = n
for(i=1;i<=n;i++) Line 1 = 1
{ a=b+c; }
Total Order= n2 +n+1
for(i=1;i<=n;i++)
Time Complexity is
{ O(n2)
for(j=1;j<=n/2;j++)
{ x1=y1+z1; }
}
}
Q.4:-
main()
{
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
for(k=1;k<=100;k++)
{ x= y+z; }
}
}
i=1 (j=i) i=2 (j=i) i=n

j=1 j=1 J=2 J=n

K K executes K executes K
executes 100 times 100 times 100 times executes
n * 100 times

1x100 2x100 n * 100


T(n)= 1 *100 + 2 *100+-------- +n *100
=100[ 1 + 2 + 3 +---------- + n ]
= 100[ n (n+1)/2]
= 100 n2
= O(n2 )
Q.5:-
main()
{
for(i=1;i<=n;i++)
{
for(j=1;j<=i2;j++)
{
for(k=1;k<=100;k++)
{ x= y+z; }
}
}
i=1 (i2 =1) i=2 (i2 = 4) i=n

j=1 j=1 J=2 J=3 J=4 J=n2

K K K K K K
executes 100 execut executes executes executes executes
times es 100 100 100 100 n2 * 100 times
times times times times

1x100 4x100 n2 * 100


T(n)= 12 *100 + 22 *100+-------- +n2 *100
=100[ 12 + 22 + 32 +---------- + n2 ]
= 100[ n (n+1)(2n+1)/6]
= 100 n3
= O(n3 )
Q.6:-
main()
{
n=
for(i=1; i<=n; i++)
{
j=2;
while(j<=n)
{
j=j2 ;
}
}
}
}
main()
Let’s take k=1, so n=4,
{
¢ when i=1, j =2
n=
ü while(2<=4) is true so
for(i=1; i<=n; i++) body will be visited once.
{ j2 = 4 (as j=2)
j=2; ü while(4<=4) is true so body
while(j<=n) will be visited again.
{ ¢ when i =2 , while body is

j=j2 ; again executed 2 times.


} we can observe that the test
condition of while depends
} only on the value of j and n
} and not i.
¢ For k=1, the for loop is executed n times and the
while body 2 times. So for loop is executed n*2
times
¢ When k=2, n=16 , the while condition becomes true
for while(2<=16) & then while(4<=16) & then
while(8<=16) & then while(16<=16) so the while
body is executed 3 times. So for k=2, for loop will be
executed n*3 times.
¢ For k=k, for loop will be executed n*(k+1) times.

so order of magnitude is nk+n i.e. nk(n is neglected).


Now will calculate value of k in terms of n
¢n = => log n = 2k log 2
=> log n = 2k = log(log n)= k log 2
=> log(log(n)) = k
So the complexity will be of the order of (nk) i.e.
O(n log(log(n))
Q. What will be the complexity of the following
code :-
A(n)
{
If(n<=1) return;
Else
Return(A(( " n))
}
a) O(n)
b) O(" n)
c) O(Log n)
d) O(log(log n))

You might also like