for (int i = 0; i < 2*n; i  ) {
   if (i == n){
     for (int j = 0; j < i; j  ) {
       for (int k = 0; k < i; k  ) {
          O(1);
       }
     }
   }
   else {
     for (int j = 0; j < i; j  ) {
       O(1);
     }
   }

The question just asks what the time complexity of the above code is. According the solutions, there is only one case and the time complexity is O(n^2).

This is how I went about solving it:

There is a for loop which nests all the other code. Within the contents of the for loop is an if statement. The if statement branches the code out into two directions. If (i==n), then it branches out into branch #1 and if (i!=n) then it branches out into branch #2.

Branch #1: for (...) --> if (...) --> for (...) --> for (...) --> O(1). Thus n(1 n ( n ( 1 ) ) ) = n n^2( n (1) ) = n n^3(1) = n n^3. This is simplified to n^3. Thus the time complexity for Branch #1 is O(n^3).

Branch #2: for (...) --> if (... ) else --> for(...) --> O(1). Thus n( 1 n(1)) = n n^2(1) = n n^2. This is simplified to n^2. Thus the time complexity for Branch #2 is O(n^2).

Therefore the worst case is branch #1, which has a time complexity of O(n^3). The best case is branch #2, which has a time complexity of O(n^2). According to the question, there is only one case and the time complexity is O(n^2). I need help knowing what I did wrong in my analysis.

CodePudding user response：

What's the area of this shape?

         n*n  
 ┌───────────────────┐ 1
 │ ┌─────────────────┘ 
 │ │
 │ │
n│ │
 │ │
 │ │
 │ │
 └─┘
  1

The area is clearly Ө(n²), not Ө(n³). Alternatively, what's the exact output of foo?

int foo(int n) {
  int ans = 0;
  for (int i = 0; i < 2 * n; i  ) {
    if (i == n) {
      for (int j = 0; j < i; j  ) {
        for (int k = 0; k < i; k  ) {
          ans  = 1;
        }
      }
    } else {
      for (int j = 0; j < i; j  ) {
        ans  = 1;
      }
    }
  }
  return ans;
}

It's 3n²-2n. To put it another way,

for (...) --> if (...) --> for (...) --> for (...) --> O(1). Thus n(1 n ( n ( 1 ) ) )

isn't tight.

CodePudding user response：

The statement if (i == n) will make the following code execute twice. The code below the if statement is On^2. 2 x On^2 is On^2

CodePudding user response：

Let us put the algorithm into some practically worded example. For example, imagine we process haystacks, and search for needles in them.

1. for (int i = 0; i < 2*n; i ) {
   Process 2*n haystacks, numbered 0, 1, ..., 2n-1.

2. if (i == n) {
   When you process the haystack number n,..

3. (the O(i²) case)
   ...be very thorough in your search.

4. } else {
   For all other haystacks,..

5. (the O(i) case)
   ...proceed normally.

In the above process, there are indeed two cases: a thorough search of haystack number n, and cursory search of every other haystack.

What is missing from your analysis that the algorithm has to do both: the one thorough case and all the cursory cases. Thus, for the person performing the algorithm, there is no choice whether to do one thorough search or many cursory searches. They have to do n cursory searches, then one thorough search, then n-1 more cursory searches, in that order.

When we talk about different cases in algorithm complexity, they are cases that depend on the input.

Imagine i was an input to our algorithm instead of a loop variable, and there was no outer for loop: as if we were told to search only one haystack, not all of them. Then your analysis would be close to the point, though no multiplying by 2n would be necessary.

But in this code, n is the only input, and i is an internal variable. So there can be no cases depending on i in the final analysis.

CodePudding user response：

Your analysis is incorrect for the following reason.

While you have correctly identified two branches with different complexity, they actually both occur ... for all values of N greater than 1.

• The first branch occurs once.
• The second branch occurs 2N - 1 times.

So since these are not different cases, there is no "best case" or "worst case".

In fact:

• The contribution to complexity of the first branch across the entire computation is 1 x O(N^2).

• The contribution second branch is (2N - 1) x O(N).

In other words, both branches are contributing O(N^2) and the overall complexity is the sum of the two contributions; i.e. O(N^2).

(Please note that my analysis is rather rough and ready ... but if someone did a rigorous analysis, I think they would get the same result.)

Another quick and dirty approach is to replace O(1) with something that just increments a counter. Run the program and for different N and graph N against the computed counts.

Or for a completely rigorous answer, do some algebra and work out the formula for the count as a function of N.