I am currently studying an algorithms unit at university and I can't seem to get a clear answer from anyone about determining the basic operation of an algorithm. I understand it can occur in more than one place, but will it be different when considering best case, average case, and worst case?

In the following example, would I be correct in assuming A[i] = Null is the basic operation for best case, as it is the one that gives the best execution time?
And is A[i] = 0 the basic operation for worst case as it's code block will have the biggest execution time? And how about average case? Will it be all 4 comparisons with the array? Like I said, I can't seem to get a clear answer from anyone. Even the textbooks I've read are incredibly vague. Any help will be very much appreciated.

for i <- 0 to n-1
    if A[i] = Null
       return
    else
       if A[i] < 0
          .....
          .....
          .....
       else if A[i] = 0
          for j <- 0 to n-1
             .....
             .....
             .....
       else if A[i] > 0
          .....
          .....
          .....

CodePudding user response：

The O notation is a function that represents the execution time a.k.a. time complexity. With increasing input size n a term will become the dominant term. The operation that is represented by this dominant term is what is called the basic operation.

Assuming all the dots in your example are O(1) these dots are your basic operation.

• In case a[0] == null the best case is O(1) (not really a case because it seems to represent missing data).
• In case a[i] == 0 for each i the worst case complexity is O(n^2).
• In case a[i] is a random value for each i the average case will be O(n) (although some values contain a zero and the average case might be a little above O(n))

CodePudding user response：

The operation that dominates the performance of an algorithm is sometimes called the basic operation. In your example, it is the evaluation of A[i]. Depending on the outcome over n iterations, the algorithm performance will differ. How is often captured by specifying three corner cases - the best, the worst, and the average. Here it depends on how frequently A[i] evaluates to zero - never, always, or on average (assuming some distribution). The performance cases are often, but not necessarily, specified using big-O notation.

So the basic operation sets the performance, and the three performance cases indicate how it plays out.