COMPUTATIONAL COMPLEXITY

Faculty of Computer Science and Engineering Department of Computer Science DATASTRUCTURES &ALGORITHMS Tutorial 1 Questions COMPUTATIONAL COMPLEXITY Required Questions Question 1. Reorder the following efficiencies from the smallest to the largest: a. 2n3 + n5 b. 2000 c. 4n+1 d. n4 e. (n-1)! f. nlog2(n) g. 2klogk(n) (k is a predefined constant) Solution: Efficiency: a measure of amount of time for an algorithm to execute (Time Efficiency) or a measure of amount of memory needed for an algorithm to execute (Space Efficiency). Non-decreasing order: 2000 < 2k logk(n) < n log2(n) < n4 < 2n3+n5< 4n+1 < (n-1)! Question 2. Determine the big-O notation for the following: a. 2n6 b. 100n + 10.5n2/3 + 5.2n5/7 c. 9log2(n) d. 5n10 + 2logn e. n! + k! (k is a predefined constant) f. 100log2(n) + 5(n+2n) Solution: a. O(n6 ) b. O(n) c. O(log2(n)) d. O(n10) e. O(n!) f. O(n) Question 3. Calculate the run-time efficiency of the following program segment: 1 i = n-1 2 loop (i >= n/2) 1 j = 1 2 loop (j < n/2) 1 print(i, j) 2 j = j + 2 3 end loop 4 i = i - 2 3 end loop Solution: (Note: [n/2] = n/2 rounded down)  If [n/2] is odd, the run-time efficiency is: n/4.n/4 = n2/2 => O(n2) Released on 03/09/2012 10:09:56 1/5 Faculty of Computer Science and Engineering Department of Computer Science  If [n/2] is even, the run-time efficiency is: n/4.(n/4-1) => O(n2) Or generally, the run-time efficiency of the given program segment is O(n2). Question 4. Calculate the run-time efficiency of the following program segment: 1 i = n3 2 loop (i >= n/2) 1 j = 1 2 loop (j < n/2) 1 print(i, j) 2 j = j + 2 3 end loop 4 i = i / 2 3 end loop Solution: There are 2 nested loops, the iteration of variable i is executed 2log2 n(n3 /2x =n/2 => x = log2n2 = 2log2n) times, j is executed n/4( or (n/4)-1) times, Therefore, the run-time efficiency is 2(log2 n)* n/4= O(nlog2(n)). Question 5. If the algorithm doIt has an efficiency factor of 2n, calculate the run time efficiency of the following program segment: 1 i = 1 2 loop (i <= n) 1 j = 1 2 loop (j < n) 1 k = 1 2 loop (k <= n) 1 doIt(…) 2 k = k *2 3 end loop 4 j = j + 1 3 end loop 4 i = i + 1 3 end loop Solution: There are 3 nested loops, the iteration of variable i is executed n times, j is executed n-1 times, k is executed log (n)+1 times. Therefore, the run-time efficiency is n(n-1)(log2(n)+1)(2n) = O(n3log2(n)). Question 6. Given that the efficiency of an algorithm is 2nlog (n4), if a step in this algorithm takes 1 nanosecond (10−9), how long does it take the algorithm to process an input of size 1024? Solution: It takes: 21024log2(1024)×10-9≈ 10360s Question 7. Released on 03/09/2012 10:09:56 2/5 Faculty of Computer Science and Engineering Department of Computer Science Write a recurrence equation for the running time T(n) of g(n), and solve that recurrence. Algorithm g (val n ) Pre n must be greater than 0 Return integer value of g corresponding to n 1 if (n = 1) 1 return 1 2 else 1 return g(n – 1)+ 1 End g Solution: T(1) = 1; T(n) = 1 + T(n-1) = 1 + 1 + T(n-2) = 1 + 1 + … + 1 + 1 + T(1) = n = O(n) Released on 03/09/2012 10:09:56 3/5 Faculty of Computer Science and Engineering Department of Computer Science Advanced Questions Question 8. Prove that for any positive functions f and g, f(n) + g(n) and max(f(n), g(n)) are asymptotically equivalent (i.e. they yield the same big-O notations). Solution: max(f(n), g(n)) ≤ f(n) + g(n) ≤ 2max(f(n), g(n)). Question 9. Estimating the time complexity of the following program segment: 1 i = 0 2 loop (i < N) 1 j = i 2 loop (j < N) 1 k = 0 2 loop (k < M) 1 x = 0 2 loop (x < K) 1 print(i, j, k) 2 x = x + 3 3 end loop 4 k = k + 1 3 end loop 4 k = 0 5 loop (k < 2*K) 1 print(k) 2 k = k + 1 6 end loop 7 j = j + 1 3 end loop 4 i = i + 1 3 end loop Solution: K%3 is 2 or 1: N*(M*(K/3)+2*K) + (N-1)*(M*(K/3)+2*K)+...+ 1*(M*K/3+2*K=N*(N+1)*(M*K/3+2*K)/2= O(N2 *M*K) K%3 is 0: N*(M*[(K/3)-1]+2*K) + (N-1)*(M*[(K/3)-1]+2*K)+...+ 1*(M*[(K/3)-1]+2*K=N*(N+1)*(M*[(K/3)-1]+2*K)/2= O(N2 *M*K) Question 10. Calculate the run-time efficiency of the following program segment: 1 i = n 2 k = n/3 2 loop (i >= k) 1 j = n – 2*k Released on 03/09/2012 10:09:56 4/5 Faculty of Computer Science and Engineering Department of Computer Science 2 loop (j < i) 1 print(i, j) 2 j = j + 2 3 end loop 4 i = i - 1 3 end loop Solution:There are 2 nested loops, the iteration of variable i is executed (2/3)*n () times, j is executed n/3 times, Therefore, the run-time efficiency is (2/3)*n*(n/3)= O(n2). Question 11. Write a recurrence equation for the running time T(n) of f(n), and solve that recurrence. Algorithm f (val n ) Pre n must be greater than 0 Return integer value of f corresponding to n 1 if (n <= 1) 1 return 1 2 else 1 return f(n – 1) + f(n – 2) End Solution: f(0) = f(1) = 1. Upper bound: f(n)=f(n-1)+ f(n-2)+1 ≤ 1+ f(n-1) + f(n-1) = 1+ 2*f(n-1)=1+ 2*[1+f(n-2)+f(n-3)]≤ 1+ 2*[1+f(n-2)+f(n-2)]= 1+2 +4*f(n-2) ≤ ...≤ 1 +2 +22 + … +2n-1 =2n -1=O(2n). Lower bound: f(n)=f(n-1)+ f(n-2)+1= f(n-2) + f(n-3) + f(n-2)≥ 1+f(n-2)+ f(n-2)= 1+ 2*f(n-2)=1+ 2*[f(n-3)+f(n-4)] ≥ 1+ 2*[1+f(n-4)+f(n-4)]=1+2 +4*f(n-4)≥...≥1+2+22 … +2n/2-1 = 2n/2-1 -1=Ω(2^(n/2) Question 12. Solve recurrence f(n) = 2f(√n) + log2n. (Hint : change variables, with m = 2n) Solution: Let m=log n => g(m)=f(2 ). Then f(n)=2f(n1/2) + log n f(2m)=2f(2m/2) +m g(m)=2g(m/2)+m We are easy to determine g(m)=2g(m/2)+m=O(m*log(m)). To change back to f(n), we have: f(n) = f(2m) = g(m) = O(m*logm) = O(log(n)*log(log(n))). -- End -- Released on 03/09/2012 10:09:56 5/5 ... - tailieumienphi.vn