CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theory
Ahmed Hamdy
Ahmed Hamdy

Reputation: 27

How to compute the time complexity of do while?

I'm trying to find the time complexity of a do while loop where there are an inner for loop. I understand how to find the complexity of the for loops, but when it comes to do while loops, I get completely lost. Any suggestions?

Below is an example of the algorithm.

M = 6
k = 1
NoItrs = 20
G_dependency = 100
alpha_dependency = 90
beta_dependency = 80
delta_dependency
do
k := k + 1
a := 2(1- k/NoItrs)
for i = 1 to M do
    Calculate b and c using Eq. 1 and 2, respectively 
    Adjust the pivot vector Y_{i_k} using Eq. 3
end for
Assign the value of the highest dependency to B_dependency
if B_dependency > alpha_dependency then
    alpha_dependency := B_dependency
else if B_dependency > beta_dependency then
    beta_dependency := B_dependency
else
    delta_dependency := B_dependency
while (B_dependency not equal G_dependency or k< NoItrs)

Upvotes: 0

Views: 197

Answers (1)

Yonlif
Yonlif

Reputation: 1790

A do while loop time complexity will be the same as the time complexity of a normal while loop (since the difference between them is not asymptotic).

As for your code - try to think of the worst case, when the while loop runs until k < NoItrs and not finishing earlier. That would mean that the time complexity (assuming all the calculations are with constant time) is O(k * M) - since for k times in the loop we do M calculations.

Upvotes: 2

Related Questions