CODEWITHSUNDEEP
c++sortingvector
Hani Goc
Hani Goc

Reputation: 2441

Find all numbers in an vector that are less than a threshold (complexity)

Let v be an unsorted vector of size n from which we want to find all numbers that are Less Than a given threshold delta.

First suggestion

#include <iostream>
#include <vector>
using namespace std;
int main()
{
   vector<int> v = {5,12,2,3,10,122,45};
   int delta = 5;
   for(size_t i = 0; i < v.size();i++){
      if(v[i] < delta){cout << v[i] << endl;}
   }
  return 0;
}

For this first solution the complexity is O(n) right?

Second suggestion

#include <iostream>
#include <vector>
using namespace std;
int main()
{

   vector<int> v = {5,12,2,3,10,122,45};
   //Sort vector v
   std::sort(v.begin(), v.end());
   int delta = 5;
   for(size_t i = 0; i < v.size();i++){
      if(v[i] < delta){cout << v[i] << endl;}
      //I added the break since it's not important anymore to find all the numbers that are greater than `delta`/
      else {break;}
   }
  return 0;
}

Questions:

  1. what is the complexity of the second algorithm?
  2. What better way to do it in c++?

Upvotes: 2

Views: 2007

Answers (1)

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39390

The idiomatic way to do that is copy_if (or remove_if) and it's indeed O(n) on an unsorted vector.

The second solution needs to sort the vector, which almost always will make the complexity worse; typical sorting algorithms work in O(n log n) (getting somewhat closer to n^2 in worst cases), and the range-knowing ones work in O(n) anyway.

The rather short and intuitive explanation is that, in any given point of traversal, because you don't know anything about the elements up front, you can't skip them and that remains until you check all of them.

Upvotes: 3

Related Questions