tailieunhanh - COMPUTATIONAL COMPLEXITY

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 | Faculty of Computer Science and Engineering Department of Computer Science DATA STRUCTURES 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 neededfor 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 3 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 jj 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 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 jj 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 dolt 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 dolt . 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 .