Computational complexity of simple algorithm

Question

I have simple algorithm, something like

h = SHA1(message)
r = a^b mod p
r = h * r mod p
l = Str1 || Str2
if ( l == r)
  return success
else
  return false

Now I want to compute its complexity, but I didn't konw how to do it. I don't know e.g. how the multiplication is done, so I don't understand how to do it. Assume worst case O(n^2) or best case or average case? Maybe I must look on it from other side?

Additionaly the numbers are keep as a byte arrays.

read [this](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — user2963623, Jul 04 '14 at 13:24
Its just whatever complexity of SHA1 is, everything else is a constant factor. — mclaassen, Jul 04 '14 at 13:26
Why it is constant factor, e.g r = a^b mod p, a and b are 256 bits(32 bytes) long, so I don't think that complexity of it is O(1)? — fliker, Jul 04 '14 at 13:32
You measure complexity w.r.t a variable. If a and b are 256 bits, a^b is doable in O(1). — user189, Jul 04 '14 at 15:53
You need to precisely define the size of the input to your algorithm before you can compute the complexity. — chepner, Jul 04 '14 at 18:25

AbcAeffchen · Accepted Answer · 2015-01-27T13:58:45.323

If you want to know the complexity of this algorithm, you just have to add the complexitys of the operations you use and sum it up.

sha1(message) has a complexity depending on the length m of the message, so lets say poly(m), since I dont know the complexity of sha1.
a^b mod p can be done in O(log b) multiplications.
h * r mod p is exactly one multiplication
Str1 || Str2 Is this bitwise or? If yes it will take O(s) where s is the length of Str1
l == r will take as much comparisons as the length of the byte array is. This will also be s.

When numbers are realy big. The can not multiplicated in one processor step, so complexity of one multiplications will be in O(log p), since log p is the length of the numbers.

All together you get O(poly(m) + log(b) ⋅ log(p) + s).

Notice: If the length of the numbers (log(b) and log(p)) will never change, this part will be constant. This also holds for s.

You said the numbers are 256 Bit long, so the complexity is only O(poly(m)), which is the complexity of the Sha1-algorithm.

Notice: If you have an algorithm with any complexity, an you only use input of a fixed length, the complexity will always be constany. Complexity is a tool to see how the runtime will expand if the input is growing. If it is not growing, the runtime will also not.
If your input has always a fixed length, than you are more interested in the performance of the implementation of an algorithm.

Computational complexity of simple algorithm

1 Answers1