Consider the following program fragments f_i with their running times t_i(n) for

Question

Consider the following program fragments f_i with their running times t_i(n) for i elementof {1, 2, 3, 4}. Give the asymptotic behavior of the running times in theta-notation. Here, the running time is defined as the number of arithmetic operations. function f_1(n): x:0; for i = 1 to n do for j = 1 to 7 do x: x + 1 end for end for return x function f_2(n): if n lessthanorequalto 121 then return 1 ft; return f_2(n/2) + 1 function f_3(n): if n lessthanorequalto 42 then return 1 fi: x: f_3(n - 1) + f_3(n - 1); return x function f_4 (n): x: 0; for i = 1 to n do for j = 1 to i do x: x + 1 end for end for return x

Explanation / Answer

f1(n)=(n*7)= (n). As 2 inner loops will get multiplied by how many times they loop.

f2(n)=as it is a recursive function with dividing the array by 2=> (logn)

f3(n)=(2n) as almost equal to fibonacci series

f4(n)= (n*i) as 2 for loops of inner.. multiplying them gets the result

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---