FOR assignment file check the attached FILE
Solution
Question 1 (10)
Find the running time complexity of the following piece of code and show your working step by step.
- 1. yz =0;
- 2. xw=0;
- 3. for(i=m; i>-6; i=i-6)
- 4. { xw++; }
- 5. for (i=n; i>-2015;i=i-5)
- 6. { yz=yz+1;}
- 7. for (i=1;i<=n;i=i*5)
- 8. { for (j=1;j<=5n;j*12
- 9. {
- a. for(k=n;k<-5; k=k-4)
- i. {
- ii. x=x+12
- iii. }
- 10. }
- 11. }
- a. for(k=n;k<-5; k=k-4)
12. Print x;
13. While(k<=z)
14. {
15. k=k*2
16. (
17. for(m=k; m<=-100000; m=m-1
18. )
19. }
- 20. Print k;
Code line number
|
Instruction/code
|
Time taken
|
Comments
|
01
|
yz =0;
|
1
|
It will take constant time
|
02
|
xw=0;
|
1
|
It will also take constant time
|
03
|
for(i=m; i>-6 i=i-6)
|
(m/2+1)+1
|
Outer independent loop1:
apply rule 2 mentioned
above in guidelines as
here step size is “2” so
value of k=2 and “m”
will control the
number of iterations
and rule gives you m/2
and base limit is “-2”
that’s why we added
“1” more here.
Note here”1” time
more than “m/2+1”is
for condition checking
at end to exit from
loop.
|
04
|
xw++;
|
m/2 +1
|
As entrance in loop is
“m/2+1” time
|
05
|
for (i=n; i>-2015;i=i-5)
|
(n/1)+1=n+1
|
Outer independent loop2:
Again apply rule 2 here step
size is “1” so value of
k=1.
Other logic is same as
in above statement “3”
only difference is of
“m” and “n” .
|
06
|
{ yz=yz+1;}
|
n
|
Entrance in a loop will be “n” times.
|
07
|
for (i=1;i<=n;i=i*5)
|
Log5n+1
|
Here step size is multiplied by 5 that’s why log to the base 5 (rule 3)
|
08
|
for (j=1;j<=5n;j*12
|
5n(log5n)+1
|
As for each iteration
of outer loop this loop
will execute for 5n times
|
09 a
|
for(k=n;k<-5; k=k-4)
| ||
09 a ii
|
x=x+12
| ||
13
|
While(k<=z)
| ||
15
|
k=k*2
| ||
17
|
for(m=k; m<=-100000; m=m-1
|
From above explanation over all time will be summed up to take
final one.
T(n)=1+1+(m/2+1)+1+m/2+1+n+1+n+log5n+1+5n(log5n)+1+(5n2
log5n) /4+1+(5n2 log5n) /4+z+1+z+…………………….
=10+2m/2+ 2n +log5n +5n (log5n) +…………………..
(10n2log5n)/4+2z 2+………………………..
Question 2 (10)
Arrange the following in the Most to Least complexity order. Here “n “is processing steps for some complexity functions and j< k and j & k are numbers greater than 2. Every function is separated by “comma”. Note: These functions must be arranged on generic basis. Further there are 20 functions to arrange and each line has five functions.
n/1000000, n
|
k /1000
|
, n
|
Log2
|
j/2
|
, 1000nLog3n , n
|
n-1000
|
,
| |||||||||||||||
n log2n
|
1000n
|
1
|
Log2
| |||||||||||||||||||
1000000000000,
|
, 2
|
,
|
(
|
n ), 100000n!,
| ||||||||||||||||||
10000
|
1000
| |||||||||||||||||||||
(n!nL og4 n), n / 12 n 2 ,n!nL og2 n /
|
n 2 ,10000L og2 (L og3n),10000,
| |||||||||||||||||||||
1000n /
|
5
|
n , n ( L og7n)
|
8
|
n ,
|
1
|
n
|
5
|
j
|
, n ( Log8 n)
|
9
|
n ,100000L og2n, 2199n
|
Log5 j/2
| ||||||||||
2150
| ||||||||||||||||||||||
Given Order
|
Most to Least Complexity Arrangements
|
n/1000000
| |
n /1000
| |
n Log2 j/2
| |
1000nLog3n
| |
n n-1000
| |
1000000000000
| |
n log2n
10000
| |
Hints to solve the above question:
- Think other way around i.e. the function which is less complex and more efficient pick it first and go ahead and then and at end reverse the order to get final arrangement ;e.g. less complex function is 1, 100, etc(Note these are constant functions that’s why these are only judged on their constant value and they fall in same class because of having constant values) Other less complex and more efficient functions are simple “log” as these functions reduce the answer for large values of “n” ; then nth root means square root cube root etc ; then linear functions are efficient and so on the logic is build .
- If you feel difficulty for comparison then judge for lager inputs say 10100 etc.
- Note 2n and n! are both complex but you can judge that n! is more complex by
putting values of larger “n” and one more thing is nn will be more complex then n! as by definition n! =n (n-1)(n-2)………..2.3.1.
But when you put the lager value in each place in above you get n(n)(n)……………n= nn which will obviously beat n!
IDEA FOR QUESTION=1 WITH EXAMPLE
Let us estimate the running time of the SelectionSort fragment
shown in Fig. 3.1. The statements have the original line numbers from Fig. 2.2. The
purpose of the code is to set small to the index of the smallest of the elements found
in the portion of the array A from A[i] through A[n-1] .
(2) small = i;
(3) for(j = i+1; j < n; j++)
(4) if (A[j] < A[small])
(5) small = j;
Fig. 3.1. Inner loop of selection sort.
To begin, we need to develop a simple notion of time units. We shall examine
the issue in detail later, but for the moment, the following simple scheme is sufficient.
We shall count one time unit each time we execute an assignment statement. At
line (3), we count one unit for initializing j at the beginning of the for-loop, one unit
for testing whether j < n, and one unit for incrementing j , each time we go around
the loop. Finally, we charge one unit each time we perform the test of line (4).
First, let us consider the body of the inner loop, lines (4) and (5). The test of
line (4) is always executed, but the assignment at line (5) is executed only if the
test succeeds. Thus, the body takes either 1 or 2 time units, depending on the data
in array A. If we want to take the worst case, then we can assume that the body
takes 2 units. We go around the for-loop n − i − 1 times, and each time around we
execute the body (2 units), then increment j and test whether j < n (another 2
units). Thus, the number of time units spent going around the loop is 4(n − i − 1).
To this number, we must add 1 for initializing small at line (2), 1 for initializing j
at line (3), and 1 for the first test j < n at line (3), which is not associated with
the end of any iteration of the loop. Hence, the total time taken by the program
fragment in Fig. 3.1 is 4(n − i) − 1.
It is natural to regard the “size” m of the data on which Fig. 3.1 operates as
m = n − i, since that is the length of the array A[i..n-1] on which it operates.
Then the running time, which is 4(n − i) − 1, equals 4m − 1. Thus, the running
time T(m) for Fig. 3.1 is 4m − 1
shown in Fig. 3.1. The statements have the original line numbers from Fig. 2.2. The
purpose of the code is to set small to the index of the smallest of the elements found
in the portion of the array A from A[i] through A[n-1] .
(2) small = i;
(3) for(j = i+1; j < n; j++)
(4) if (A[j] < A[small])
(5) small = j;
Fig. 3.1. Inner loop of selection sort.
To begin, we need to develop a simple notion of time units. We shall examine
the issue in detail later, but for the moment, the following simple scheme is sufficient.
We shall count one time unit each time we execute an assignment statement. At
line (3), we count one unit for initializing j at the beginning of the for-loop, one unit
for testing whether j < n, and one unit for incrementing j , each time we go around
the loop. Finally, we charge one unit each time we perform the test of line (4).
First, let us consider the body of the inner loop, lines (4) and (5). The test of
line (4) is always executed, but the assignment at line (5) is executed only if the
test succeeds. Thus, the body takes either 1 or 2 time units, depending on the data
in array A. If we want to take the worst case, then we can assume that the body
takes 2 units. We go around the for-loop n − i − 1 times, and each time around we
execute the body (2 units), then increment j and test whether j < n (another 2
units). Thus, the number of time units spent going around the loop is 4(n − i − 1).
To this number, we must add 1 for initializing small at line (2), 1 for initializing j
at line (3), and 1 for the first test j < n at line (3), which is not associated with
the end of any iteration of the loop. Hence, the total time taken by the program
fragment in Fig. 3.1 is 4(n − i) − 1.
It is natural to regard the “size” m of the data on which Fig. 3.1 operates as
m = n − i, since that is the length of the array A[i..n-1] on which it operates.
Then the running time, which is 4(n − i) − 1, equals 4m − 1. Thus, the running
time T(m) for Fig. 3.1 is 4m − 1
