1-ADA.Intro
1-ADA.Intro
1-ADA.Intro
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
K K executes K executes K
executes 100 times 100 times 100 times executes
n * 100 times
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