-1
$\begingroup$

For a selection problem, for example select $k$ smallest items from a list of unsorted array of real numbers, to assess the performance of a algorithm how is the time complexity calculated? Is it evaluated based on a specific value of $k$ or is it averaged across all possible values of $k$? That is $k \in \mathbb{N}, 0\lt k \lt n$.

My currently understanding is that the complexity is calculated based on single value of $k$ but it may be unfortunate.

I've asked a related question here but the accepted answer doesn't explicitly point out this.

Improve this question
$\endgroup$
1
  • $\begingroup$ Establishing tight resource requirements bounds on problems means proving something about all possible algorithms, possibly for one single abstract machine model. $\endgroup$ Commented Dec 23, 2024 at 16:51

1 Answer 1

Reset to default
0
$\begingroup$

It depends on the algorithm, but some algorithms promise that the running time will be at most $O(n)$, regardless of the value of $k$. Thus, this is a worst case over all $k$. As a result, this running time bound can be applied for any specific value of $k$ you have in mind (it says that $O(n)$ time applies simultaneously for all $k$). See https://en.wikipedia.org/wiki/Selection_algorithm, https://en.wikipedia.org/wiki/Median_of_medians.

I don't know of any algorithm whose running time is obtained by averaging over $k$. Some algorithms are evaluated by averaging over all random choices made by the algorithm (all its internal coin tosses).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your explanation. One more thing I want your help is about the output of the selection algorithm in case the requirement is to return a collection of $k$ smallest values instead of just the $k$th smallest value. In this case, does the output have to be sorted? $\endgroup$ Commented Dec 25, 2024 at 6:12
  • $\begingroup$ @KtStudent, en.wikipedia.org/wiki/Selection_algorithm defines the selection problem clearly $\endgroup$ Commented Dec 25, 2024 at 6:23
  • $\begingroup$ @KtStudent Sometimes yes, sometimes no. Ask the person who gave the task. $\endgroup$ Commented Dec 25, 2024 at 11:33

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.