Computing worst case time complexity with algorithms

Question

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).

PZwan · Accepted Answer · 2016-04-04 02:48:50Z

1

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

answered Apr 4, 2016 at 2:48

PZwan

1012 silver badges6 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lamar Latrell Over a year ago

While very practical, I think the question (and questioner) is looking for a bit more of an analytical approach

Community · Accepted Answer · 2017-05-23 12:15:50Z

1

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³)

edited May 23, 2017 at 12:15

CommunityBot

11 silver badge

answered Apr 4, 2016 at 2:57

Igor Moura

432 silver badges7 bronze badges

4 Comments

Lamar Latrell Over a year ago

While true, the loop indices are kind of interesting, perhaps worth mentioning?

Paul Ogdee Over a year ago

Thanks, I just had trouble finding other questions that used pseudo code instead of actual code. It's just easier for me to understand that way.

Igor Moura Over a year ago

@LamarLatrell Since it is the worst case, I believe it is safe to assume the value of the indices are sort of irrelevant and can be seen simply as n. Correct me if I'm wrong.

Lamar Latrell Over a year ago

You're correct in the complexity/big-Oh case. I now see the links, apologies, I didn't see them on the mobile interface I was just using... They sit in place of what I was suggesting.

Collectives™ on Stack Overflow

Computing worst case time complexity with algorithms

2 Answers 2

1 Comment

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related