I'm learning about Big-O Notation and algorithms to improve my interview skills, but I don't quite understand how to get the time complexity.

Suppose I want to sum all the elements of the following list.

std::vector<int> myList = {1,2,3,4,5} ;

Case 1:

int sum = 0;
for (int it: myList)
{
  sum  = it;
}

Case 2:

int sum = std::accumulate(std::begin(myList), std::end(myList), 0);

Case 1 is O(N), and case 2 is apparently O(1), but I'm sure those functions do some kind of iteration, so the question is whether Big-O notation is calculated only from of the written code of that block or also of the functions used.

CodePudding user response：

If you talk about big-O, you have to talk in respect of some unit of data being processed. Both your case 1 and case 2 are O(N) where N is the number of items in the container: the unit is an int.

You tend to want the unit - and N to be the count of - the thing that's likely to grow/vary most in your program. For example, if you're talking about processing names in phonebooks, then the number of names should be N; even though the length of individual names is also somewhat variable, there's no expected pattern of increasing average name length as your program handles larger phonebooks.

Similarly, if your program had to handle an arbitrary number of containers that tended to be roughly the same length, then your unit might be a container, and then you could think of your code - case 1 and case 2 - as being big-O O(1) with respect to the number of containers, because whether there are 0, 1, 10 or a million other containers lying around someone in your program, you're only processing the one - myList. But, any individual accumulate call is O(N) with respect to any individual container's ints.

CodePudding user response：

I think this example should give you an idea.

int sum(std::vector<int> const& list)
{
   int result = 0;
   for( elem const& : list )
   { 
       result  = elem;
   }
   return result;
}

int main()
{
   std::vector<int> test = {1,2,3,4,5,6};
    

   // O(n)
   int sum1 = 0;
   for( elem const& : test )
   {
      sum1  = elem;
   }

  // O(???)
  int sum2 = sum(test);
}