constant time complexity: O(x^c)

162 views Asked by At

I know if we use constant number of operation our time complexity is constant.

so what if we have following scenario:

for example an operation uses an array of fixed size 1000. no matter what that operation or what size of the input is the amount of computation will always be (1000 ^ 1000) (the computation is regardless of the size of input)

can we still say that its time complexity still O(1) , even our number of operation is (1000^1000)?

3

There are 3 answers

0
harold On

Yes, any constant. That "big O" thing is a set of functions, following this definition

f(x) ϵ O(g(x)) <-> ∃m,c ∀n≥m f(n) ≤ c g(x)

As you can see here, you may simply pick c as your huge constant, and thereby put it in the class O(1).

That should not be taken as a statement about real life performance, for obvious reasons.

5
AudioBubble On

Absolutely. As N increases, the computation time stays constant. When doing asymptotic analysis, the value of that constant does not matter.

0
skrtbhtngr On

Yes, I think so.

Complexity is mainly used to indicate the order of growth of your algorithms. That is, how you algorithm will scale if the input is increased. Now, given that the space and time used by your algorithm are constant regardless of the input, we can say that it has constant space or time complexity.