a) Calculate the number of times the following loop executes for i-1 to 2n for j

Question

a) Calculate the number of times the following loop executes for i-1 to 2n for j to 2n-1 do something without branching nextj next i (3 marks) b) Assuming that n is the input size and that "do something without branching" in the innermost loop of part a) involves 100 calculations, state the order of complexity of the entire calculation using big O notation. (3 marks) c) Another algorithm executes 2n log n+ 3 calculations for an input of size n. (i) Is this algorithm O(n')? ii) State the complexity of the algorithm using big omega notation.

Explanation / Answer

a) Loop will run for

=> 1 + 2 + 3 + ....2n - 1

=> 1+ 2 + 3...n + n+1 + n+2....2n
=> n(n+1)/2 + n(n+1)/2
=> n(n+1)


b) Even if "do Something withoput branching is executed 100 calculation", Still the time complexity

will be 100*n*(n+1) = O(n2)



c) i ) Yes n2 is asymptotic larger than n log n so its O(n2)
ii) Using big Omega its (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.