TAILIEUCHUNG - 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 .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.