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?