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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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).