2. (10 points) For each of the program fragments below, let T(n) represent, wors

Question

2. (10 points) For each of the program fragments below, let T(n) represent, worst-case, the execution time of that program fragment in terms of n, an input value to each fragment (a) (1 points) Fragment: for i-1 to n for j-1 to n end Worst-case, the above fragment takes ( time (b) (3 points) Fragment for i-1 to n int[] array - new int[1000]; Worst-case, the above fragment takes time (c) (3 points) Fragment for i-1 to n int[] array = new int [i] ; end Worst-case, the above fragment takes time. (d) (3 points) Fragment for i-1 to n if Math.random)

Explanation / Answer

Hello there,

a) i will explain these complexity step by step, here outer loop will be executed n times and inner loop will also be executed n times, inner statement will take constant time, so in worst case time complexity will be theta(n2).

b) In second question, outer loop will be executed in n times, however, inner statement is creating an array of size 1000 each time but on very large scale or for very large value of n , it is negligible or considered as constant time, so in worst case time complexity will be theta(n).

c) In 3rd question, again outer loop will be executed in n times, and in this also, inner statement is creating an array of size 'i',( which increases with 'n') each time but on very large scale or for very large value of n ,this is also negligible or considered as constant time,so in worst case time complexity of this also will be theta(n).

d) In 4th question, again outer loop will be executed in n times, and inside of it there is one if condition, which seems to be negligible but inside of this if, there is one loop which will be executed in n time and have one constant time statement, but in this situation we can not ignore this statement inside loop and if conditionm also. since inside of outer loop, there is one inner loop so ultimately, worst case time complexity of this will be theta(n2).

Hope, you will get your solution, feel free to ask any queries and to give feedback.

Thank you

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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