Answer with justification and testing the codes For each function state its best

Question

Answer with justification and testing the codes For each function state its best and worst case asymptotic run time with respect to n. Assume all arithmetic operates in constant time. Justify your answers for full credit. (a) Function (n) for i = 1 to n do for j = 1 to 100 Print("help") (b) Function (n) for i = 1 to n do for j = i downto 1 Print("help") (c) Function (n) for i = 1 to n j = i do while j > 1 j = Floor(j/2) Print("help") (d) Function (n) if n = 1 then return 3 else m = Function(Floor(n/2)) h = Function(Floor(n/2)) k = Function(Floor(n/2)) return m+h+k

Explanation / Answer

4.

a)

1. First loop will iterate for n times
2. Second loop will iterate for 100 times constantly
and print step will take constant time.
So Best and worst case will be same here
O(n*100) = O(n)

b)

1. First loop will iterate for n times
2. Second loop will iterate for ith times each time
and print step will take constant time.
so total time complexity will be
1+2+3+....+n = n*(n+1)/2. So O(n^2)

c)

1. First loop will iterate for n times
2. Second loop will iterate for log(i) times each time
and print step will take constant time.
so total time complexity will be nlog(n)
Second loop always reduced by 2. So thats why time complexity is logn

d)
Each inside function will take log(n) to execute
So total time compelxity will be log(n) + log(n) + log(n) = 3*log(n) = log(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.