Complexity of Function

[L1bXjE8b]

I am a bit confused about the Big-O complexity of this function:

void permute (int a[], int n)
{
  bool* used = new bool[n];//O(1)
  fill (used, used+n, false);//O(1)
  for (int i = 0; i < n; i++)//O(n)
    {
      a[i] = rand() % n;//??
      while (used[a[i]])//???
        {
         a[i] = rand() % n; //O(1)
        }
      used[a[i]] = true; //O(1)
    }
  delete [] used;//Since there are no destructors, is this O(n) or O(1)?
}

See the comments in the code for my assumptions and observations.

I am unsure about the two middle lines. Since they are both dealing with arrays, I'm not sure if they should be O(1) or O(n). Also, I don't understand if the pcode]delete[][/code] should be O(1) or O(n). I have found conflicting information on this online. Any help would be appreciated.

[helios]

The time complexity of both line 7 and line 10 is implementation-defined. The standard does not define a time complexity for rand(). In most implementation, rand() takes O(1).

Depending on the definition of used(), the loop on line 8 may or may not terminate. AFAIK, there's no guarantee that rand() will ever return a given value. For example, this may be an infinite loop:

while (rand() != 0);

Because this is a valid implementation of rand():

int rand(){
    return 1;
}

[L1bXjE8b]

So, would it be safe to assume that the entire function is O(n)?

[helios]

No. Like I said, it depends on the definition of used() and on the implementation of rand().

[AbsentMindedProf]

I respectfully request that people stop responding to CSundergrad's posts. He's a student in my course, knows that all work he submits for grading is supposed to be his own, but has been getting the helpful people in this Forum to write virtually every line of code for him in his programming assignments and, now, would like you to do his analysis work for him as well.