CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
Atirag
Atirag

Reputation: 1740

Complexity of this algorithm

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?

Upvotes: 0

Views: 97

Answers (2)

Ming
Ming

Reputation: 4290

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.

Upvotes: 1

ashley
ashley

Reputation: 1175

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.

Upvotes: 3

Related Questions