CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
Konrad
Konrad

Reputation: 2287

Possible meanings of n in O(n) notation?

In the question here, many posters keep on referring to larger inputs, when talking about increasing n. Therefore, some of them say that an algorithm with O(1/n) complexity cannot exist. Now, lets say we have an algorithm where we specify that we want a list of size n by removing elements from an existing list of size m (therefore removing m - n elements, and n <= m obviously) . Clearly, increasing n leads to reduced computation times, as larger n implies less operations.

So does n then have to refer to the physical size of an input (like the size of the input list in a sorting algorithm) or can it be defined more abstractly as here?

I know that big O notation is defined for asymptotic behaviour, but what if we have an algorithm where a parameter n is clearly bounded from above, as it is here? Can we just say we assume n < m?

I know the example above is very silly, but I actually have a case (which is too complicated to post here, hence the silly example, but it has some parallels to this example) where computation time clearly decreases as n increases, and n is also bounded from above, and defining it differently such that it isn't bounded from above is not possible.

Thanks in advance

Upvotes: 1

Views: 299

Answers (2)

HenryLee
HenryLee

Reputation: 406

I'll use a conventional notation to re-demonstrate your example. We want a list of size k by removing elements from an existing list of size n. In this example, k is different from n, because n is the input size but k is just a parameter.

Depending on implementation, this problem can be done in either O(k) or O(n-k). If it's O(n-k) implementation, the increase of your input size still results in higher complexity. If it's O(k), the complexity of your algorithm depends on only a parameter but no input size. Either way, your input size doesn't attribute to the decrease of the complexity of the algorithm.

Yes, some algorithms have complexity that depends on only a parameter k, but not an input size n, given that we know what the parameter k is (or it can be computed in a trivial time). It's widely used in solving NP-complete problems. Parameterized complexity

But, I still don't know any algorithms that is O(1/n) where n is the size of the input.

Upvotes: 1

Alex Hall
Alex Hall

Reputation: 36043

In the case of your example you would say that the running time of the algorithm is, say, O(m-n) (or perhaps O(log(m-n)) or O((m-n)^2) depending on how each item is removed), so that you can actually convey the complexity in a useful manner. There is probably a way to reframe your problem to do this. The entire point of the notation is to concisely express the scalability of an algorithm. I expect you can find some function of the various parameters of the problem which expresses the 'difficulty' of the input (e.g. m-n) which may be something more abstract than size, and then a function of that difficulty (e.g. x^2) which converts the difficulty into space or time requirements.

Upvotes: 1

Related Questions