CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theory
Steven Redding
Steven Redding

Reputation: 15

What is the best case time complexity of the following algorithm?

I am given the following function, where g is some other function that runs in Θ(n²). What is the best case time complexity for this function?

void f(int n) {
  if(n % 2 == 0) {
    return;
  } else {
    g(n);
  }
}

Clearly, the function runs in constant time if n is even, which tempts me to say Θ(1), but I don't think that's the correct answer because I don't think that's how an asymptotic tight bound is defined.

I've looked at a lot of similar questions on SO regarding big theta notation and best case analysis, but they all pertain to arrays of length n inputs, rather than just an integer. I think the best case analysis makes sense in those cases because it depends on the elements in the array.

However there is no analog to "elements in the array" for this question that seems to matter in determining the complexity other than g, whose complexity is fixed.

This leads me to conclude that the actual best case time complexity is Θ(n²). Is my understanding correct? Is it Θ(n²) or Θ(1)?

Upvotes: 0

Views: 1332

Answers (2)

user1196549
user1196549

Reputation:

I don't agree with @aksingh's answer.

From the given,

  • when n is even, all of the best case, worst case and plain running times are Θ(1), and

  • when n is odd, all of the best case, worst case and plain running times are Θ(n²).

In fact, there is no difference between the three times (in the asymptotic sense), because of the Θ.

It is important to notice that the function that describes these running times need not be "a single expression".

If you want to obtain results that do not depend on parity, you can write that the best, worst and plain case running times are Ω(1) and O(n²).

To illustrate, the plot shows some hypothetical running times (red dots). In green and magenta, the best and worst cases, for odd n. In blue, even n.

enter image description here

Now in gray, the best case function.

enter image description here

Upvotes: 0

Anuj
Anuj

Reputation: 1665

You seem quite confused in the usage of Θ notation.

I don't think that's the correct answer because I don't think that's how an asymptotic tight bound is defined.

Θ notation is an asymptotic tight bound and it may be defined as:

For any two functions f(n) and g(n), we have f(n) = Θ(g(n) if and only if
f(n) = O(g(n)) and f(n) = Ω(g(n)).

O notation gives an asymptotic upper bound and Ω notation gives an asymptotic lower bound.

In the algorithm you provided,

 void f(int n) 
 {
     if(n % 2 == 0) return;
     else g(n);
 }

where g(n) = Θ(n²).

The running time of the algorithm belongs to both O(n²) and Ω(1). We cannot use the Θ notation to describe the running time of your algorithm if we are considering all the possible values of n.

However, if we look at the running time of the algorithm when the only value that n can take is even, which is the best case, then we can say that in the best case, the running time of the algorithm belongs to both O(1) and Ω(1). Hence, we can say that the best case complexity of the algorithm is Θ(1).

Do notice the difference between saying,

The running time of the algorithm is Θ(1). //Wrong in this case

and

The best case running time of the algorithm is Θ(1). //Correct in this case

Similarly, if we look at the running time of the algorithm when the only value that n can take is odd, then we find out that worst case complexity of the algorithm is Θ(n²).

I hope I have helped you.

Upvotes: 1

Related Questions