Doubt about constant-time sorting algorithms

Asked

Viewed 182 times

6

I need to solve a exercise with the following statement:

As input we have a vector of n elements, where each element has a value between 0 and k. In addition we have two integer values to and b. We must answer how many elements in the input vector have interval value [to,b]. Design an algorithm whose complexity is O(1) for this problem.

I can’t imagine any algorithm with constant complexity to solve this. The fastest I know (linear ordering) do not meet because they are of complexity O(n). Would it be possible to solve this problem with complexity O(1)? Or is there an error in the statement?

algorithm
  • 2

    I haven’t started anything yet because I haven’t thought of any algorithm. The fastest I know (linear ordering) do not meet because they are of complexity O(n). It would be possible to solve this problem with complexity O(1)?

  • Do you want someone to do your exercise? Besides, you didn’t explain anything, you didn’t show what you already did, you didn’t talk about language. Try to do something, then explain better what your doubt, what language, paste the code and we can help.

  • 4

    Gustavo, welcome to the site. I edited your question to solve two problems, which led to votes against and to close: (1) the questions here need to be self-sufficient, and yours required a visit to an external link; (2) it looked like you were asking to solve your homework, and from your comments I understood that the problem is different, so I edited accordingly. If you disagree, you can change it again, or reverse my edit.

  • 1

    @Paulomaciel Eu think that the question wasn’t quite what it looked like, take a look at the issue I did.

  • @bfavaretto now became clearer, before he only asked to solve an exercise without making clear the problem

  • 1

    Thank you very much people! I am new here and did not know very well how it worked, thank you very much for the help and sorry anything! =)

  • You are welcome! This site really works a little different from the others, I suggest doing the tour and take a look at help center.

  • 1

    I know an algorithm to perform the sum of n numbers of any vector in O(lg n) time, but for this it needs a previous preparation process to assemble a table, whose time is O(n). Supposing the statement is correct, wouldn’t that be the case that the teacher asks? It may be that the requested algorithm has a longer preparation time than O(1), but then, during operation, it has O(1)... Almost how a hash table works? I’m curious now!

Show 3 more comments

2 answers

5

I can’t give you a rigid mathematical test, but I say with certainty that what is asked is impossible. For any case not trivial:

  • k < 0 (only admits the empty vector with input, the return is zero)
  • a > k (the return is always zero)
  • b < 0 (the return is always zero)
  • b < a (the return is always zero)
  • a = 0 E b = k (the return is always n - assuming that the size of the vector can be determined in constant time)

it is possible to produce two distinct vectors:

  • V + [x], where x ∈ [a,b]
  • V + [y], where y ∉ [a,b]

which will produce different results if evaluated by this function.

Suppose there is an algorithm with complexity O(1). So, for vectors of size greater than or equal to n0 there is a constant K such that the running time is less than or equal to K. Be it V the vector (one of the vectors? ) whose runtime is the longest of all (i.e. K), and whose return value is R. How this algorithm would evaluate V + [_]?

  • If it does not perform any operation additional to those it has already performed to evaluate V, then he can’t say deterministically if the result is R or R + 1 - since the additional element may be at least x or y;
  • If it performs one or more additional operations, then its run time is greater than K (assuming an operation has run time greater than zero). That is, the algorithm has no order of complexity O(1), as an assumption.

By the way, this also means that - contrary to the assumption - the vector V was not in fact the one who possesses the "longest execution time of all". In fact, such a vector does not exist - since the set of all possible vectors with elements of 0 to k is infinite (even if enumerable). Any vector you choose as "the largest" can - as demonstrated - give rise to a vector whose runtime is at least one elementary operation greater than it.

The best algorithm that solves this problem will have complexity of O(n). It is inevitable that all elements of the vector are visited at least once - either to compare, or to include in a count, or to be the object of an arithmetic operation. Unless there is some "catch" I’m not seeing, this exercise has no solution...

0

Good people, thank you very much. I used a little of every piece of information you left here to compose my answer. In the end I divided it into two cases: 1º Whereas there are methods that will go through and determine the amount of elements that are between [a, b] and call my complexity method O(1) passing the correct amount. 2º Considering that a < 0 and b > k, in this case my complexity method O(1) would return the size of the vector because all the elements will be in this interval. I will talk to the teacher about this question and put the result here later. Thank you so much again.

Browser other questions tagged algorithm

You are not signed in. Login or sign up in order to post.