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

Question

Consider the following program fragments f_i with their running times for t_i(n) for i {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: return f_2(n/2) + 1 function f_3(n): if n lessthanorequalto 42 then return 1: 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:

It is nested loop. For ever 'i', j varies from 1 to 7 i.e. 7 times. Since 'i' varies from 1 to 'n', so total operations are 7*n times

x=7*n = theta(n)

f2:

Say n<=121, no arithmetic operation is performed.

Say If n>121, x=theta (log(n))

f3:

f4:

For each 'i' , j varies from 1 to i. So it becomes 1+2+...+n i.e. x=n(n+1)/2 = theta(n*n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---