How do I determine the basic operation of this algorithm?

Question

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 < n and A[i] ≠ K do
 {
 i ←i + 1
 }
 if i < 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?

• Raphael: Some of our reference questions may be of help. Bottom line, "basic operations" are whatever you choose.
• KeizerHarm: "Whatever I choose" is not of much help in a homework assignment where my professor specifically has one in mind above the other... The reference questions page is very interesting, and I found a couple articles there that I want to read later, but for this particular problem they are not of help. 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. But if I am mistaken I would love to hear.

Answer 1

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

• KeizerHarm: I appreciate your answer, really. I just feel like saying "either would work" is less likely to be accepted. I could round up a long explanation about that either would work given all the facts you and I mentioned, but there is also a language barrier between me and the professor so it may easily be misunderstood, if it is not an answer he would have expected.
• KeizerHarm: So could I ask you if, looking at the algorithm, you would not see a difference in using either of the two operations as basic operations? Because maybe I just misread the syntax and in that case this whole issue is much simpler.
• Raphael: @KeizerHarm I think you already answered your question there. You're saying you get the same result; so why would there be a difference? Trust in your work! (Unless proven wrong, of course.) That said: No, I don't think you're misreading the syntax. And, again: if you want to play it safe, just count both. However, note that comparisons i < n are another dominant operation.

Answer 2

Yes, You will get different results base on what you choose as your basic operation. Following this view, this result makes no sense.

To choose a basic operation is to choose a constant unit to measure the complexities between different algorithms. It's like once you want to compare whether China or France is further from you, You can choose miles, meters even the hours you went there as your unit.

So just ensure you choose the same unit between the algorithms which you want to compare, then you can choose whatever you want. And don't forget your conclusion based on your choice may be various.