How do I determine the basic operation of this algorithm? Admissions:


Yes, this is a homework assignment.
No, this is not me trying to outsource my homework to the internet.


I am honestly fazed by my teacher's explanation of the "basic operation", and the internet is not helpful either. I get lists that say what a basic operation can be (e.g. assignment, multiplication, comparison), and what it is used for (determining time complexity) but not how to determine it for a given algorithm.

Here is the algorithm in question.

// Problem: Search a given value K in a given array A by sequential search
//Input:  array A[0..n − 1] and a search key K
//Output: The index of the first element in A that matches K and −1 if there are no matching elements.

SequentialSearch(A[0..n − 1], K)
{
   i ←0
  while i &lt; n and A[i] ≠ K do
  {
    i ←i + 1
  }
  if i &lt; n  
     return i
  else 
   return −1
}


The question: is the basic operation assignment, or comparison?

Candidates that I see:


Comparison: A[i] ≠ K
Assignment: i ←i + 1


The problem is that both of these would work to determine time complexity. The comparison is executed 1 time in best-case and n times in the worst-case scenario. The assignment is executed 0 times in best-case and n-1 times in worst-case. Towards infinity, constants do not matter, so really they both work equally well.

So the irony is that I know the time complexity of this algorithm, but not the basic operation which I am supposed to determine to figure out the time complexity.

What is the logic to use here to figure out which one is the basic operation, and which one isn't?
"Basic operations" are whatever you choose. You may get different results based on your choice, which is great as it leads to understanding algorithms better! You may have seen the number of comparisons and swaps being analyzed independently in array sorting algorithms. 

As a corollary, your professor can pick whatever they want. We can't possibly know their mind; you'll have to ask them. 

That said, if you're after "time complexity", you want to count how often a dominant operation occurs. See here and here (section "A note on asymptotic cost"). In case of doubt, just count all candidate operations. 


  Getting different results based on my choice is something I also think is not applicable here, as the two options I am struggling between have identical results in when going towards infinite input sizes.


In that case, the choice doesn't matter. Either both operations are dominant and your result is correct, or they are both not and you need to pick another operation entirely.