Algorithms and data structures(CS2321) assignment 2 solution

Kingdom of Saudi Arabia ‫المملكة العـربية السعودية‬
Ministry of Higher Education ‫وزارة التعليم العالي‬
Prince Sattam bin Abdulaziz University ‫جامعة األمير سطام بن عبدالعزيز‬
College of Computer Engineering and Sciences ‫كلية هندسة وعلوم الحاسب‬
Computer Science Department ‫قسم علوم الحاسب‬
Course Title: Data Structures and Algorithms (CS2321) / 1438-1439 (1)
Homework 2 (Solutions)
(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A D C D B D D A C D C B C B C B
(2)
Sort the following functions in the decreasing growth rate:
3 N 2 3
N, N log N, N log log N, N log N, 2 , 2 , N log N, N
1 2 3 4 5 6 7 8
N 3 2 3
2 N N log N N log N N log N N log log N 2
N

(3)
Let the two functions f ( n )=n2 and g ( n )=4 n log n. Complete the following table:
n f (n) g( n)
2 4 8
4 16 32
8 64 96
16 256 256
32 1024 640
64 4096 1536
128 16384 3584
What is the turning point of the two functions f (n) and g( n)?
The Turning point is n=16 we can see that f ( n )=g ( n )=256. If n<16 , f ( n )< g ( n ) and If n>256 , f ( n )> g ( n )
Compare the growth rate of the two functions f (n) and g( n)?
The growth rate of f (n) is faster than the growth rate of g( n) .
(4)
1. The running time for this fragment is O(N).
Proof
N −1
∑ 1=N
i=0
2. The running time for this fragment is O(N2).
Proof
N −1 N−1 N−1
∑ ∑ 1= ∑ N=N . N =N 2
i=0 j=0 i=0


CS2321 – Homework 2 Page 1/2

, 3. The running time for this fragment is O(N3).
Proof
2
N −1 N −1 N −1
2 2 3
∑∑ 1 = ∑ N =N . N =N
i=0 j=0 i=0

4. The running time for this fragment is O(N2).
Proof
N −1 i−1 N −1 N−1
(N −1) N N 2−N
∑ ∑ 1= ∑ i= ∑ i= 2
=
2
i=0 j=0 i=0 i=1
5. The running time for this fragment is O(N5).
Proof
2
N −1 i −1 j−1 N −1 i 2 −1 N −1 2 2 N −1
(i −1 )i 1
∑ ∑ ∑ 1 =∑ ∑ j =∑ = ∑ (i4 −i2 )
i=0 j =0 k=0 i=0 j=0 i=0 2 2 i=0
N−1 N −1
=
1
2 [∑ i=0
i 4− ∑ i2

2
i=0
]
1 N ( N +1)(2 N +1)(3 N +3 N −1) N ( N +1)(2 N +1)
=
2 30[ 2
−
6 ]
1 N ( N +1)(2 N +1)(3 N +3 N −1)−5 N ( N +1 )(2 N +1 )
=
2 30 [ ]
1
= [ N ( 2 N 2 +3 N +1)(3 N 2 +3 N −1)−5 N ( 2 N 2 +3 N +1 ) ]
60
1
= [ 6 N 5 + polynomial in deg ree 4 ]
60

6. The running time for this fragment is O(N4).
Proof
j−1
∑ 1= j
The innermost loop running time is . k =0

The middle loop is executed only if j is a duplication of i. Then the running time for it is i
i i
i(i+1) i 3 +i
∑ li=i ∑ l=i 2
=
2 . Thus the total running time is
+ 2i + 3i + … + i2 = l=1 l=1
N −1 3 N −1 N−1
∑ i2 +i =12 ∑ i3+ ∑ i
i=1
2 2
[ i=1 i=1 ]
1 N ( N −1) ( N −1)N
=
2 4
4
[3
+
2
2 ]
N −2 N +3 N −2 N
=
8
Then the running time is O(N4).




CS2321 – Homework 2 Page 2/2