-2
$\begingroup$

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?

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

3 Answers 3

1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ I am expecting an explanation from the downvoter. $\endgroup$ Feb 25 at 21:47
  • $\begingroup$ 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. $\endgroup$ Feb 25 at 22:21
  • 1
    $\begingroup$ @EJoshuaS-ReinstateMonica: don't worry, this is common on StackExchange. $\endgroup$ Feb 26 at 9:00
  • 1
    $\begingroup$ @YvesDaoust Just so you know, I did not downvote your post 😅 $\endgroup$ Feb 26 at 16:35
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.