Complexity of this algorithm

Question

So I have an algorithm that goes like this:

for i=0:360

 C...

 for j=0:a_j[i]

   C...

   for t=0:a_t[i][j]

     C...
   end
 end
end

So I have three loops but both inner loops depend on the value of the outer loops. How can I measure its Big O notation complexity?

Also what if I have memory asignments between these loops? Are they counted as Cs?

It's impossible to say, because we don't know what a_j and a_t are. — Oliver Charlesworth
– Oliver Charlesworth, Commented Jun 6, 2013 at 17:13
If this is basically for i = 0 to 360; for j = 0 to i; for t = 0 to j;, then complexity is O(n ^ 3). — user529758
– user529758, Commented Jun 6, 2013 at 17:15

ashley · Accepted Answer · 2013-06-06 17:19:42Z

3

You are not saying anything about the rest of the code, so assuming the rest is primitive operations of constant complexity.

If the entries of the two arrays are less than a constant value, then the complexity is O(1)-- the processing does not depend on any value input from outside your code. If they are functions of an input variable, then the complexity depends on the functions they are processed into those arrays and in this case you have to be more specific.

answered Jun 6, 2013 at 17:19

ashley

1,1831 gold badge14 silver badges17 bronze badges

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

2 Comments

Atirag Over a year ago

Ok I get it. The arrays do depend on an input variable. There are many operations done inside the innermost array. For example a sum of all the values of t into a result[i][j] and several others like that.

ashley Over a year ago

You have to be specific what those operns are. Depends still.

Ming · Accepted Answer · 2013-06-06 17:45:03Z

1

I'm not sure what a_j and a_t are exactly. If a_j and a_t are constant, then the complexity are O(1). If a_j and a_t are the n, which may means input variables, then we have to compute the complexity.

In a word, the complexity of this program is decided by how you define a_j and a_t.

Anyway, I can compute how many loops that your program executes.

Here is the code written in python:

ret = 0
for i, v in a_j:
    ret += v * sum(a_t[i])
if not ret: ret = 1
ret *= 360

Hope it helps.

answered Jun 6, 2013 at 17:45

Ming

4,3101 gold badge32 silver badges34 bronze badges

Collectives™ on Stack Overflow

Complexity of this algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related