CODEWITHSUNDEEP
algorithmmathtimecase
Paul Ogdee
Paul Ogdee

Reputation: 11

Computing worst case time complexity with algorithms

this is a question on my study guide, but I'm unsure how to begin the problem, or even what the code "to n do" means. I've seen some other questions be answered that are also looking for worst case time complexity, but nothing with code similar to this problem. I'm just looking for a general way to solve these problems, so if there's a go to method, I would really like some help. The question is below.

Compute the worst case time complexity of the following algorithm.

for i = 1 to n do
    for j = 1 to i do
        for k = 1 to j do
            print(i,j,k).

Upvotes: 0

Views: 111

Answers (2)

Igor Moura
Igor Moura

Reputation: 43

This question has been answered some times already, you can check them here and here for the mathematical explanation.

Basically, since it is a triple nested loop, the worst time would be 0(n³)

Upvotes: 1

PZwan
PZwan

Reputation: 101

It seems to me that there is no best or worst case time complexity in this case, just the time complexity. As mentioned in this wikipedia article, the best and worst cases are generally applicable to functions such as sorting functions, where the time taken by the algorithm would be dependent upon how the input was initial sorted. Thus in your case, following the results of the matlab code below, I would say that the time complexity is

1/6*n*(n+1)*(n+2)

This was arrived at by running the code for different values of n, and noting that each increment to n adds the corresponding triangle number of print statements, i.e.

sum_{i = 1}^{n} 1/2*i*(i+1) = 1/6*n*(n+1)*(n+2)

Matlab code:

n = 5;

count = 0;
for i = 1:n
    for j = 1:i
        for k = 1:j
            count = count + 1;
        end
    end
end

1/6*n*(n+1)*(n+2)
count

Upvotes: 1

Related Questions