I'm not entirely sure the Big O complexity of this

Question

This will find the nth element in an unsorted array as if it was sorted, and I want it to run below n log n time, but I'm not entirely sure the run time of this, would it be O(n^2)?

int nthElement(std::vector<int> vec, int n)
{
  n--;
  int smallest = vec[0];
  int index = 0;
  for(int i = 0; i < vec.size(); i++)
  {
    if (vec[i] < smallest)
    {
      smallest = vec[i];
      index = i;
    }
  }
  vec.erase(vec.begin() + index);
  if( n == 0)
  {
    std::cout << "Do I get here?" << std::endl;
    return smallest;
  } 
  return nthElement(vec, n);
}

Yes, O(n^2). One n for the for loop and one n for the tail recusion. — Klaus Gütter, Jan 05 '19 at 07:05
@Damien `O(n x size)`, size being a constant, would reduce to simply `O(n)` — chickity china chinese chicken, Jan 05 '19 at 07:14
Let us assume n=2 and size=10000... It is O(n^2) if we assume that n can take any value lower than size. Generally, we estimate the complexity relatively to the size of the problem, and generally we call `n` or `N` this size.... The ambiguity comes from that. Complexity is O(size^2), O(N^2) if we call `N` this size — Damien, Jan 05 '19 at 07:35

score 0 · Accepted Answer · answered Jan 05 '19 at 08:17

Ask yourself what's n compared to vec.size(). Assuming n is kind of random between 0 and vec.size()-1, the following holds true:
- in the best case, n = 0.
- in the worst case, n = vec.size().
- in the average case, n ~ vec.size() (~ means proportional).

So the time complexity, in general, is indeed O(n^2) = O(vec.size()^2) = O(n*vec.size()).

I'm not entirely sure the Big O complexity of this

1 Answers1