CSC 3323 - Algorithm Analysis
Practicing problems
Mohamed Ennahdi El Idrissi
Summer 2012
1)
a. For the following fragments, give the exact number of iterations and the time complexity:
sum = 0;
for ( i = 0 ; i < n ; i ++) {
sum ++;
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < n ; j ++) {
sum ++;
}
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < n * n ; j ++) {
sum ++;
}
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i =
sum
}
for ( j =
sum
}
0 ; i < n ; i ++) {
++;
0 ; j < n * n ; j ++) {
++;
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i =
sum
}
for ( j =
sum
}
0 ; i < n ; i += 2 ) {
++;
0 ; j < n * n ; j ++ ) {
++;
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < i ; j ++) {
sum ++;
}
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; i < n ; i ++ ) {
for ( j = 0 ; j < n * n ; j ++ ) {
for ( k = 0 ; k < n ; k ++ ) {
sum ++;
}
}
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; 2 * i < n ; i ++ ) {
sum ++;
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = n ; i > 0 ; i -- ) {
sum ++;
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 1 ; i < n ; i = i * 2 ) {
sum ++;
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 1 ; i * i <= n ; i ++ ) {
for ( j = 1 ; j <= i ; j = j * 2 ) {
sum ++;
}
}
--------------------------------------------------------------------------------------------------------------------------------------
b. The following code fragments afford an amelioration that would affect positively the
performances. Where can you apply this amelioration?
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < n * n ; j ++) {
sum ++;
}
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i =
sum
}
for ( j =
sum
}
0 ; i < n ; i ++) {
++;
0 ; j < n * n ; j ++) {
++;
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i =
sum
}
for ( j =
sum
}
0 ; i < n ; i += 2 ) {
++;
0 ; j < n * n ; j ++ ) {
++;
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; i < n ; i ++ ) {
for ( j = 0 ; j < n * n ; j ++ ) {
for ( k = 0 ; k < n ; k ++ ) {
sum ++;
}
}
}
-------------------------------------------------------------------------------------------------------------------------------------sum = 0;
for ( i = 0 ; 2 * i < n ; i ++ ) {
sum ++;
}
--------------------------------------------------------------------------------------------------------------------------------------
sum = 0;
for ( i = 1 ; i * i <= n ; i ++ ) {
for ( j = 1 ; j <= i ; j = j * 2 ) {
sum ++;
}
}
-------------------------------------------------------------------------------------------------------------------------------------2) Resolve the following recursion relations and find their time complexity:
a. T(n) = T(n - 1) + c
b. T(n) = T(n 1) + nc
c. T(n) = T(n / 2) + c
d. T(n) = 2T(n/2) + cn
e. T(n) = 2T(n - 1) +
c
2
f. T(n) = 3T(n/2) + cn
g. T(n) = 2T(n/2) + cn log n
h. T(n) = T(n - 2) + c
i. T(n) = T(n - 1) + T(n - 2) + c
j. T(n) = 3T(n / 3) + cn
k. T(n) = 2T(n / 2) + n / log n
l. T(n) = 2T(n - 1) + c
m. T(n) = 4T(n/2) + n log2 n
n. T(n) = T(n) + c
o. T(n) = 2T(n) + log2 n
p. T(n) = 2
i=0
n - 1 T(i)
+ 1
q. T(n) = 1/n
i=0
n - 1 T(i)
+ n
r. T(n) = 2/n
i=0
n - 1 T(i)
+ n
r. T(n) =
i=0
n - 1
i * T(i) + n
3) Graph theory: Topological Sort
a. This graph illustrates a sample of the courses offered by AUI's Computer
Science department. Apply the topological sort on this graph (show steps).
b. Why is it possible to use topological sort on this graph?
4. Graph Theory: DFS, BFS, MST, Shortest Path
Use DFS (a) and BFS (b) to traverse the graph thoroughly, with the constraint of
visiting the cities only once (show the steps).
MST: A telecommunication company would like to establish a wired network.
- using both Prim's (c) and Kruskal (d), show the steps of connecting all
the cities (vertices) of the graph below.
Shortest Path: using Dijkstra (e), Bellman-Ford (f), and Floyd (g), find the
shortest path, knowing that the starting point is Agadir, and the destination is
Oujda.
Solutions:
When a loop increment is addition/subtraction, the formula to apply is:
(n - k) / m
where
for ( i =
; i <
; i +=
);
sum = 0;
for ( i = 0 ; i < n ; i ++) {
sum ++;
}
Applying the formula above, we get:
(N - 0) / 1 = N,
Therefore the running time is:
sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < n ; j ++) {
sum ++;
}
}
Outer loop:
(N - 0) / 1 = N
Inner loop:
(N - 0) / 1 = N
Therefore the running time is:
O(N)
N * N ->
sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < n * n ; j ++) {
sum ++;
}
}
Outer loop:
(N - 0) / 1 = N
Inner loop
(N * N - 0) / 1 = N
Therefore, the running time is:
N * N =
sum = 0;
for ( i = 0 ; i < n ; i ++) {
sum ++;
}
for ( j = 0 ; j < n * n ; j ++) {
sum ++;
}
O(N)
O(N3)
First loop:
(N - 0) / 1 = N
Second loop:
(N * N - 0) / 1 = N
Therefore, the running time is:
O(N) + O(N) =
O(N)
sum = 0;
for ( i =
sum
}
for ( j =
sum
}
First loop:
(N - 0) / 2 = N / 2
Second loop:
(N * N - 0) / 1 = N
Therefore, the running time is:
0 ; i < n ; i += 2 ) {
++;
0 ; j < n * n ; j ++ ) {
++;
O(N) + O(N) =
O(N)
For nested loops, which indexes depend on the index of the immediately outer loop,
the formula is as the following:
n ( n + 1 ) ( n + 2 ) ... ( n + r - 1 ) / r! =
Where c is the number of operations,
number of nested loops.
sum = 0;
for ( i = 0 ; i < n ; i ++) {
for ( j = 0 ; j < i ; j ++) {
sum ++;
}
}
is the number of elements, and
is the
Since the nested loop depends on the index
of the outer loop:
We have n, the number of, elements and r is
the number of nested loops:
Therefore, the exact number of iterations
would be:
n ( n + 1 ) / 2! = (
- n ) / 2
therefore, the running time is:
O(N)
sum = 0;
for ( i = 0 ; i < n ; i ++ ) {
for ( j = 0 ; j < n * n ; j ++ ) {
for ( k = 0 ; k < n ; k ++ )
{
sum ++;
}
}
}
sum = 0;
for ( i = 0 ; 2 * i < n ; i ++ ) {
sum ++;
}
Outermost loop:
(N - 0) / 1 = N
First inner loop:
(N * N - 0) / 1 -> N
Innermost loop:
(N - 0) / 1 = N
Therefore, the running time is
O(N * N * N) =
O(N4)
We have 2 * i < N = i < N / 2
Therefore, ((N / 2) - 0) / 1 = N / 2
This loop will iterate N / 2 times.
O(N)
sum = 0;
for ( i = n ; i > 0 ; i --) {
sum ++;
}
Applying the formula above, we get:
(0 - N) / -1 = N,
Therefore the running time is:
O(N)
When a loop increment is multiplication/division, the formula to apply is:
(Logm (n / k) )
where
for ( i =
sum = 0;
for ( i = 1 ; i < n ; i = i * 2 ) {
sum ++;
}
; i <
; i *=
);
(Log2 (n / 1)) -> (Log2 n)
When n = 8,
3
the loop will iterate Log2 2 = 3 times.
When n = 10,
the loop will iterate Log2 10 = 3.3219280949
-> 4 times.
sum = 0;
for ( i = 1 ; i * i <= n ; i ++ ) {
for ( j = 1 ; j <= i ; j = j * 2 ) {
sum ++;
}
}
Outer loop:
We have i * i < N -> i < N
(N - 1) / 1 -> N - 1
Inner loop:
(Log2 (i / 1)) -> (Log2 i).
For the inner loop, we notice that
its number of iterations depend on
i:
When i = 1, Log 1 -> 0 iterations;
When i = 2, Log 2 -> 1 iteration;
When i = 3, Log 3 -> 1 iteration;
...
When i = N, Log2 N
And we know that:
i=1
N log i = N Log N
Since we are dealing with N instead
of N, the time complexity is:
O(N Log N)
2.
a.
T(n) = T(n - 1) + c
T(n) = (T(n - 2) + c) + c
T(n) = ((T(n - 3) + c) + c) + c
T(n) = T(n - 3) + 3c
...
T(n) = T(n - k) + kc
when n - k = 0 -> n = k, and T(0) = 1
T(n) = T(0) +
nc
Therefore, the time complexity is
O(N)
b.
T(n) = T(n 1) + nc
T(n) = (T(n - 2) + (n - 1)c) + nc
T(n) = ((T(n - 3) + (n - 2)c) + (n - 1)c) + nc
T(n) = T(n - 3) + cn - 2c + cn - c + nc
T(n) = T(n - 3) + 3cn - 2c - 1c - 0c
...
T(n) = T(n - k) + kcn - c(i
= 0
k - 1
i)
T(n) = T(n - k) + kcn - c( (k - 1)(k) / 2 )
T(n) = T(n - k) + kcn - ck / 2 - ck / 2
when n - k = 0 -> n = k, and we have T(0) = 1
T(n) = T(0) + cn - cn / 2 - cn / 2
T(n) = T(0) + c
/ 2 - cn / 2
Therefore, time complexity is
c.
O(N).
T(n) = T(n / 2) + c
T(n) = (T(n / 2) + c) + c
3
T(n) = ((T(n / 2 ) + c) + c) + c
...
k
T(n) = T(n / 2 ) + kc
k
when n / 2 = 1, n = 2 then k = log2 n
T(n) = T(1) + c
log2 n
Therefore the time complexity is
O(log2 n).
d.
T(n) = 2T(n/2) + cn
T(n) = 2(2T(n/2) + cn/2) + cn
3
T(n) = 2(2(2T(n/2 ) + cn/2) + cn/2) + cn
3
T(n) = 2 T(n/2 ) + 2cn/2 + 2cn / 2 + cn
...
T(n) = 2 T(n/2 ) + kcn
k
when n / 2 = 1, n = 2 so k = log2 n
log n
T(n) = 2
n log2 n
T(1) + c
Therefore, the time complexity is
O(N Log N)
e.
T(n) = 2T(n - 1) +
T(n) = 2(2T(n - 2) +
c) + c
T(n) = 2(2(2T(n - 3) + c) + c) + c
3
T(n) = 2 T(n - 3) + 3c
...
k
T(n) = 2 T(n - k) + kc
when n - k = 0, n = k
T(n) =
2nT(0)
+ nc
The time complexity is
f.
T(n)
T(n)
T(n)
T(n)
=
=
=
=
O(2n)
(Non polynomial -> Algorithm to be discarded).
3T(n/2) + cn
2
2
3(3T(n/2 ) + cn / 2) + cn
3
2
3(3(3T(n/2 ) + cn / 2) + cn / 2 + cn
3
3
2
1
0
0
3 T(n/2 ) + 3cn / 2 + 3 cn / 2 + 3 cn / 2
...
k
k-1
T(n) = 3 T(n/2 ) + 3
k
T(n) = 3 T(n/2 ) + cn
k
cn / 2
i=0
k-1
+ 3
k-2
cn / 2
k-2 ...
+ 3 cn / 2
k-1 3i/2i
when n/2 = 1, n = 2 -> k = log2 n
+ cn (i=0
log n
T(n) = 3
T(n)
T(n)
<=
<=
log n
(3
3 /2 )
<= 3log n
2
i=0
3 /2
) + O(n )
The time complexity is
O(n).
k-1 3i/2i [i=0k-1 (3/2)i]
The formula of i=0
demonstration below:
+ cn
) + cn [1 / (1 - 3/2)]
log 3
(n
((log n) - 1)
was found through the
Thus
Refer to the Zeno Summation.
g.
T(n)
T(n)
T(n)
T(n)
T(n)
...
=
=
=
=
=
2T(n/2) + cn log n
2(2T(n/2) + cn/2 log n/2) + cn log n
3
2(2(2T(n/2 ) + cn/2 log n/2) + cn/2 log n/2) + cn log n
3
3
1
1
1
0
0
0
2 T(n/2 ) + c2 n/2 log n/2 + c2 n/2 log n/2 + c2 n/2 log n/2
3
3
1
0
2 T(n/2 ) + cn log n/2 + cn log n/2 + cn log n/2
T(n) = 2 T(n/2 ) + cn (i=0
k
k-1
log n/2 )
when n/2 = 1, k = log2 n
log n
T(n) = 2
(log n) - 1 log
(log n) - 1
log
i=0
i=0
T(n) =
T(1) + cn (i=0
(log n) - 1
log n/2 )
(log n) - log 2 log n/2i)
i
(log n/2)
i
n/2 ) = i=0
log n/2 )
(log n/2)
(n) + cn (i=0
log n - log
i
n/2 ) =
i=0
2)
we have log 2 = i log 2 = i
T(n) = (n) + cn (i=0
(log n/2)
(log n/2)
i=0
(log n) - i
=
=
=
=
=
=
=
(log n) - i)
(log n) - i=0
i
log2 n/2 * log2 n - [(log2 n/2) * (log2 n/2 + 1) / 2]
(log2 n - 1) log n - [(log2 n - 1) (log2 n - 1 + 1)/2]
(log2 n - 1) log2 n - [(log2 n - 1) (log2 n)/2]
log2 n - log2 n - 1/2log2 n + 1/2log2 n
1/2log2 n - 1/2log2 n
1/2 (log2 n - 1) log2 n
(log n/2)
i=0
(log n/2)
T(n) = (n) + cn (1/2 (log2 n - 1) log2 n)
T(n) = (n) + cn (log2 (n))
Therefore, the time complexity is
(n log2 n)
h.
T(n)
T(n)
T(n)
T(n)
...
T(n)
when n - k
T(n)
=
=
=
=
T(n - 2) + c
(T(n - 4) + c) + c
((T(n - 6) + c)) + c) + c
T(n - 6) + 3c
= T(n - k) + ck/2
= 0 -> n = k
= T(0) + cn/2
T(n) = 1 + cn/2
(n)
Therefore, the time complexity is
i.
T(n) = T(n - 1) + T(n - 2) + c
we consider the following:
T(n - 2) + T(n - 2)
<=
T(n - 1) + T(n - 2)
|
(X)
(Y)
<=
|
Lower bound
>=
>=
>=
>=
2T(n - 2) + c
2(2T(n - 4) + c) + c
2(2(2T(n - 6) + c) + c) + c
3
2
1
0
2 T(n - 6) + 2 c + 2 c + 2 c
k
>= 2 T(n - (2*k)) + 2
k-1
c + 2
k-2
c + ... + 2 c
T(n) >= 2 T(n - (2*k)) + i=0 c
When n - 2*k = 0 -> n = 2k -> k = n/2
k
k-1
T(n) >= 2 T(0) + i=0
n/2
T(n) >= 2 + cn/2
n/2
(n/2)-1
Therefore, the time complexity for this case:
(2n)
O(Z):
T(n)
T(n)
T(n)
T(n)
...
<=
<=
<=
<=
2T(n - 1) + c
2(2T(n - 2) + c) + c
2(2(2T(n - 3) + c) + c) + c
3
2
1
0
2 T(n - 3) + 2 c + 2 c + 2 c
k
T(n) <= 2 T(n - k) +
When n - k = 0 -> n = k
n
T(n) <= 2 T(0) +
n
T(n) <= 2 + cn
i=0
i=0
k-1 c
n-1 c
Therefore, the time complexity for this case:
O(Z)
upper bound
(X):
T(n)
T(n)
T(n)
T(n)
...
T(n)
T(n - 1) + T(n - 1)
Since (2 ) = O(2 ) -> The time complexity is
O(2n)
(2n).
k.
T(n)
T(n)
T(n)
T(n)
T(n)
T(n)
...
T(n)
T(n)
=
=
=
=
=
=
2T(n/2) + n / log2 n
2
2(2T(n/2 ) + n / 2 / log2 n / 2) + n / log2 n
3
2
2
2(2(2T(n/2 ) + n/2 / log2 n / 2 ) + n / 2 / log2 n / 2) + n / log2 n
3
3
2
2
2
1
1
1
0
0
0
2 T(n/2 ) + 2 n/2 /log2 n/2 + 2 n/2 /log2 n/2 + 2 n/2 / log2 n/2
3
3
2
1
2 T(n/2 ) + n/log2 n/2 + n/log2 n/2 + n / log2 n
3
3
2)
2 T(n/2 ) + n/(log2 n - log2 2 + n/(log2 n / log 2) + n / log2 n
k
k-1
k-2
...
= 2 T(n/2 ) + n/(log2 n-log2 2 ) + n/(log2 n-log 2 )
+ n / log2 n - 0
k
k
...
= 2 T(n/2 ) + n/(log2 n- k - 1) + n/(log2 n- k - 2)
+ n / log2 n - 0
T(n) = 2 T(n/2 ) +
i=0
(k - 1) n
/ ((log2 n) - i)
when n/2 = 1, k = log2 n
log n
T(n) = 2
T(1) +
T(n) (n) + n
j=1
i=0
log n/2 n
log n
/ ((log2 n) - i)
1 / j
T(n) (n) + n log2 log2 n
The time complexity is
why
i=0
log n/2 n
(n log2 log2 n).
/ ((log2 n) - i) n
j=1
log n 1
/ j ?
Assume that n = 8, log2 8 = 3, we thus would have 2 iterations ((log2 8) - 1).
i=0
(log 8/2) n
/ ((log2 8) - i) =
3
when i = 0,
when i = 1,
when i = 2,
i=0
(log 8/2) n
8 / (log2 2 - 0) = 8 / 3
3
8 / (log2 2 - 1) = 8 / 2
3
8 / (log2 2 - 2) = 8 / 1;
/ ((log2 8) - i) = 8 / 3 + 8 / 2 + 8 / 1;
8 * (j=1
1 / j) =
when j = 1, 1 / 1 = 1 / 1
when j = 2, 1 / 2 = 1 / 2
when j = 3, 1 / 2 = 1 / 3
log 8
8 *
j=1
log 8 1
Hence,
i=0
/ j = 8 (1/1 + 1/2 + 1/3) = 8/1 + 8/2 + 8/3
log n/2 n
/ ((log2 n) - i) n(j=1
log n
1 / j).
When n is not a power of 2 (because, in our case, the logarithm is of base 2), the
first series yields a value that is greater than the second series.
For instance, when n = 1023,
log 1023
- 1
log 1023
- 1
i=0
log 1023
- 1
i=0
1023 / ((log2 1023) - i) = 1023.00/9.9986 + 1023.00/8.9986 + 1023.00/7.9986 +
1023.00/6.9986 + 1023.00/5.9986 + 1023.00/4.9986 + 1023.00/3.9986 + 1023.00/2.9986 + 1023.00/1.9986 +
1023.00/0.9986.
i=0
1023 / ((log2 1023) - i) = 102.3144 + 113.6845 + 127.8975 + 146.1723 + 170.5401
+ 204.6577 + 255.8402 + 341.1603 + 511.8608 + 1024.4440.
1023 / ((log2 1023) - i) = 2998.58
1023(j=1
log 1023
1 / j) = 1023/1 + 1023/2 + 1023/3 + 1023/4 + 1023/5 + 1023/6 + 1023/7 + 1023/8 +
1023 / 9 + 1023 / 10.
1023(j=1
log 1023
1023(j=1
log 1023
1 / j) = 1023.0000 + 511.5000 + 341.0000 + 255.7500 + 204.6000 + 170.5000 +
146.1429 + 127.8750 + 113.6667 + 102.3000.
1 / j) = 2996.33.
The table below displays the values of the series 1 and the series 2 parallelly
when n = 1023.
iteration
Series 1
Series 2
1/10
102.3144
102.3000
2/9
113.6845
113.6667
3/8
127.8975
127.8750
4/7
146.1723
146.1429
5/6
170.5401
170.5000
6/5
204.6577
204.6000
7/4
255.8402
255.7500
8/3
341.1603
341.0000
9/2
511.8608
511.5000
10/1
1024.4440
1023.0000
We notice above that all the values of the first series are larger than the second
one.
The table below displays the values of the series 1 and the series 2 parallelly
when n = 1025.
Iteration(i/j)
Series 1
Series 2
1/10
102.4856
102.5000
2/9
113.8711
113.8889
3/8
128.1025
127.1250
4/7
146.3991
146.4286
5/6
170.7932
170.8333
6/5
204.9423
205.0000
7/4
256.1598
256.2500
8/3
341.5064
341.6667
9/2
512.1394
512.5000
Here, we notice that all the values of the second series are larger than the first
one.
Conclusion:
i=0
log n/2 n
/ ((log2 n) - i) = n
j=1
log n 1
/ j, when n is a power of 2.
/ ((log2 n) - i) >= n j=1
1 / j, when n smaller than the nearest
value that is a power of 2 (for instance: 1023, 2047 ...).
i=0
log n/2 n
log n
/ ((log2 n) - i) <= n j=1
1 / j, when n larger than the nearest
value that is a power of 2 (for instance: 1025, 2049 ...).
i=0
log n/2 n
l.
T(n)
T(n)
T(n)
T(n)
...
T(n)
log n
=
=
=
=
2T(n - 1) + c
2(2T(n - 2) + c) + c
2(2(2T(n - 3) + c) + c) + c
3
2
1
0
2 T(n - 3) + 2 c + 2 c + 2 c
k
= 2 T(n - k) + 2
k-1
c + 2
k-2
c + ... + 2 c
T(n) = 2 T(n - k) + i=0
2
when n - k = 0, n = k and T(0) = 1
k
k - 1
T(n) = 2 T(0) + i=0
2
n
n
T(n) = (2 ) + 2 - 1
n+1
n
T(n) = 2
- 1 = (2 ) - 1
n
n - 1
Therefore, the time complexity is
(2n).
(Non polynomial)
10/1
1023.5586
1025.0000
m.
T(n)
T(n)
T(n)
T(n)
T(n)
...
T(n)
k
when n/2 =
T(n)
T(n)
T(n)
=
=
=
=
=
4T(n/2) + n log2 n
4( 4T(n/2) + n/2 log2 n/2 ) + n log2 n
3
4( 4(4T(n/2 ) + n/2 log2 n/2) + n/2 log2 n/2 ) + n log2 n
3
3
4 T(n/2 ) + 2n/2 log2 n/2 + 2n/2 log2 n/2 + n log2 n
3
3
4 T(n/2 ) + 3 n log2 n
=
1
=
=
=
4 T(n/2 ) + knlog2 n
log
-> k = log2 n, and we know that 4
nT(1) + knlog2 n
(n) + n log2 n log2 n
2
(n) + n log2 n.
Therefore, the time complexity is
= 2
log n
log n
-> 4
= n
(n log22 n ).
1/2
n.
T(n) = T(n) + c = T(n) = T(n ) + c
1/4
T(n) = (T(n ) + c) + c
1/8
1/8
T(n) = ((T(n ) + c) + c) + c = T(n) = T(n ) + 3c
k
T(n) = T(n^1/2 ) + kc
k
k
We have n^1/2 = 2, and let's assume that X = 1/2
X
1/X
k
k
n = 2, n = 2 -> n = 2^2 -> log2 n = 2 .
Now let's assume that Y = log2 n:
k
2
Y = 2 -> k = log2 Y which means that k = log2 log2 n = log2 n.
2
Hence, T(n) = T(2) + c log2 n.
Therefore, the time complexity is
o.
T(n)
T(n)
T(n)
T(n)
T(n)
T(n)
=
=
=
=
=
=
(log22 n).
1/2
2T(n) + log2 n = T(n) = 2T(n ) + log2 n
1/4
1/2
2(2T(n ) + log2 n ) + log2 n
1/8
1/4
1/2
2(2(2T(n ) + log2 n ) + log2 n ) + log2 n
3
3
2
1
1/2
2 T(n^1/2 ) + 2 log2 n^1/2 + 2 log2 n
+ log2 n
3
3
2
1
2 T(n^1/2 ) + 2 * 1/2 log2 n + 2 * 1/2 log2 n + log2 n
3
3
2 T(n^1/2 ) + 3 log2 n
...
k
T(n) = 2 T(n^1/2 ) + k log2 n
k
k
T(n) = 2 T(n^1/2 ) + k log2 n
k
k
We have n^1/2 = 2, and let's assume that X = 1/2 :
X
1/X
k
k
n = 2 -> n = 2
-> n = 2^2 -> log2 n = 2 -> k = log2 log2 n
log log n
T(n) = 2
T(2) + log2 n log2 log2 n
T(n) = (log2 n) + (log2 n log2 log2 n).
Therefore, the time complexity is:
(log2 n log2 log2 n)
4.a Topological Sort
Initial Graph
CSC 1401 had no in-edges.
CSC 1401 is the first element to be selected, and therefore
eliminated with its out-edges.
this time, CSC 2302 is the next selected element.
So far, the topological sort result is:
CSC 1401 -> CSC 2302
For the next element, we can choose CSC 2303, CSC 2304, or CSC 3324
to pursue the process. We opt for CSC 2303, hence we notice that
three vertices have no edges, those are going to be included in the
topological sort list in the next step.
The list so far is:
CSC 1401 -> CSC 2302 -> CSC 2303
Getting rid of the three vertices that have no in or out edges:
CSC 1401 -> CSC 2302 -> CSC 2303 -> 3315 -> 3323 -> 3309
Getting rid of the three vertices that have no in or out edges:
CSC 1401 -> CSC 2302 -> CSC 2303 -> 3315 -> 3323 -> 3309 -> 2304
CSC 1401 -> CSC 2302 -> CSC 2303 -> 3315 -> 3323 -> 3309 -> 2304 ->
CSC 3351
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338 -> CSC 3326 -> CSC 5301
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338 -> CSC 3326 -> CSC 5301 -> CSC 3325 ->
CSC 3327
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338 -> CSC 3326 -> CSC 5301 -> CSC 3325 ->
CSC 3327 -> CSC 3353
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338 -> CSC 3326 -> CSC 5301 -> CSC 3325 ->
CSC 3327 -> CSC 3353 -> CSC 5366
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338 -> CSC 3326 -> CSC 5301 -> CSC 3325 ->
CSC 3327 -> CSC 3353 -> CSC 5366 -> CSC 5365
The final result is:
CSC 1401 > CSC 2302 > CSC 2303 > CSC 3315 > CSC 3323 > CSC 3309
> CSC 3352 -> CSC 2304 > CSC 3351 > CSC 5304 > CSC 5339 ->
CSC 3324 -> CSC 5338 -> CSC 3326 -> CSC 5301 -> CSC 3325 ->
CSC 3327 -> CSC 3353 -> CSC 5366 -> CSC 5365 -> CSC 5368 ->
CSC 5378
This result is one among many other results. Once more than one
vertex has no in-edge, we can choose a vertex arbitrarily and come
up with an ordering. Any choice is correct.
4.b Topological sort is applicable for this graph, because it is a
DAG).
Directed Acyclic Graph (
Dijsktra Shortest Path
Agadir
0
Safi
Marrakech Ouarzazate
292Agadir
249Agadir
364Agadir
292Agadir
364Agadir
Settat
Beni Mellal Casablanca Khouribga Errachidia
Rabat
Meknes
Azrou
Midelt
Larache
Fez
Taza
Oujda
417Marrakech 444Marrakech
453Marrakech
364Agadir
417Marrakech 444Marrakech
537Safi
453Marrakech
417Marrakech 444Marrakech
537Safi
453Marrakech 663Ouarzazate
444Marrakech
485Settat
453Marrakech 663Ouarzazate
485Settat
453Marrakech 663Ouarzazate
485Settat
663Ouarzazate
695Khouribga
663Ouarzazate 578Casablanca 695Khouribga
663Ouarzazate
695Khouribga
745Rabat
695Khouribga
804Errachidia
745Rabat
1193Errachidia
765Meknes 804Errachidia
745Rabat
755Meknes
1193Errachidia
765Meknes 804Errachidia
765Meknes 804Errachidia
928Fez
1193Errachidia
804Errachidia
928Fez
1193Errachidia
928Fez
1193Errachidia
1193Errachidia
Therefore, we notice that, through backtracking starting from the destination (Oujda), the shortest path is:
Oujda -> Errachidia -> Ouarzazate -> Agadir
The red weights suggest that a shorter path was found from a different vertex.
755Meknes 1096Larache 1193Errachidia
References
- [Link]
- [Link]
-[Link]
- Data Structures and Algorithm Analysis, 3rd edition - Mark Allen Weiss
- [Link]
- [Link]
- [Link]
- [Link]