# Is O(k*n) in this case linear?

Problem: find sum of k element in array and it is biggest? time complexity of my algorithm is O(k*n).Is it linear complexity?

• "and it is biggest": what does that mean ? Feb 25 at 9:22
• It may be helpful in this case to have a minimal reproducible example illustrating the code or pseudocode you were trying. Feb 25 at 22:32
• @Yves Daoust it means find kth largest elements. Feb 28 at 2:30
• Do you mean the k largest elements ? Feb 28 at 7:41

Yes, the algorithm is linear in $$k$$ and linear in $$n$$, whatever $$k$$ and $$n$$ mean. But it is quadratic in $$(k,n)$$.

• I am expecting an explanation from the downvoter. Feb 25 at 21:47
• I'm curious too.. someone downvoted all of the answers, though, so maybe they don't like us answering the question. Still a bit irritating, it's my first answer here. Feb 25 at 22:21
• @EJoshuaS-ReinstateMonica: don't worry, this is common on StackExchange. Feb 26 at 9:00
• @YvesDaoust Just so you know, I did not downvote your post 😅 Feb 26 at 16:35

By definition, time complexity of a problem is defined due to its input size (please check this section on Wikipedia).
As input, you get an array of length $$n$$ ($$O(n)$$) and ONE number $$k$$ ($$O(1)$$), so that the input size of your problem is $$O(n)$$ in overall. On the other hand, the time complexity of your algorithm is $$O(kn)$$ so that you can't call that algorithm linear.

I'm going to challenge the premise of the question: your algorithm should be O(n), so either your implementation is wrong or your analysis of the complexity is wrong. This is a solution to this that is definitely O(n) (or, to be more precise, $$\theta(n)$$ because the loop will always take exactly n steps):

public void LargestAndSum(int[] numbers, int k)
{
int sum = 0;
int largest = int.MinValue;
for (int i = 0; i < numbers.Length; i++)
{
if (i < k)
{
sum += numbers[i];
}

if (numbers[i] > largest)
{
largest = numbers[i];
}
}

Console.WriteLine(\$"Sum: {sum}. Largest: {largest}");
}


It's tempting to look at the i < k part and say "see? It's O(kn)!" However, this isn't true, and the reason is the following: it does the i < k comparison exactly n times. The operation in the loop happens k times (where $$k \le n$$), so that term is dominated by n. So there are two comparisons that will happen exactly n times, an addition operation that will happen $$k \le n$$ times, and an assignment operation that will happen at least once (in the case where the first number is the largest in the array) and at most n times (in the case that numbers is sorted in ascending order). Therefore O(n).

Side note: obviously in actual production code you would want to validate that $$numbers \neq null$$ and $$k \le n$$ because it wouldn't make sense for $$k > n$$. I did not include the argument validation in the code, though.

You may also want to read this Q&A on the difference between O(kn) and O(n + k).

• I think you misunderstanding my question. My problem is find kth largest elements in array. Feb 28 at 2:39
• Ex: input n=7, aray: 9 4 2 5 3 8 1 and k=3. then output is 9 5 8 Feb 28 at 2:41