Please, can anyone help with this question? It\'s a C++ data structure question

Question

Please, can anyone help with this question? It's a C++ data structure question from one of the books. The topic is about "Time Complexity"

Thank you. Much appreciated.

Question 3: Give the exact operation count for function F hereafter, counting every assignment, comparison, addition, etc. as 1 operation, and knowing that the "if test succeeds half the time. Show all details and justify as necessary. Indicate accordingly the worst/best time complexity of this function. (5 marks) void F (int aD, int n) llargs: array a[] of size n for (int k n/2, k 0, k/ 2) for (int j 30: j

Explanation / Answer

Average Case:

Outer for loop will be executed log(n/2) times.

Total operations = log(n/2)*[Cost for inner for loop] + (cost for updating value of k)*log(n/2)

= log(n/2)*[Cost for inner for loop] + (1)*log(n/2)

As given if test succeds half the times,Inner for loop will be executed n/2 times.

So, Cost for inner for loop = n/2 * [3*assignments + 1*comparision + 1*(cost for updating value of j) ]

=n/2 *[ 3 + 1 + 1 ]= 5n/2

So,

Total operations =  log(n/2)*[5n/2] + log(n/2)

= O(nlogn)

Worst Case:

Total operations = log(n/2)*[Cost for inner for loop] + (1)*log(n/2)

worst case will happen when all the if statements are not true.

so in that case, Cost for inner for loop =n*[ 3 + 1 + 1 ]= 5n

Total operations = log(n/2)*[5n] + (1)*log(n/2)

= O(nlogn)

Best Case:

Total operations = log(n/2)*[Cost for inner for loop] + (1)*log(n/2)

best case will happen when all the if statements are true.

so in that case, Cost for inner for loop = cost for if statement = 1

Total operations = log(n/2)*[1] + (1)*log(n/2)   

= 2*log(n/2)

= O(logn)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---