Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Complexity of std::find_end as Big-O

How can I represent the complexity of std::find_end algorithm as Big-O notation?

The complexity of std::find_end is defined as follows:

At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applications of the corresponding predicate.

like image 858
hotwatermorning Avatar asked Nov 14 '12 00:11

hotwatermorning


People also ask

What is big O time complexity?

What is Big O? Big O, also known as Big O notation, represents an algorithm's worst-case complexity. It uses algebraic terms to describe the complexity of an algorithm. Big O defines the runtime required to execute an algorithm by identifying how the performance of your algorithm will change as the input size grows.

Is time complexity the same as Big O?

The Big O Notation for time complexity gives a rough idea of how long it will take an algorithm to execute based on two things: the size of the input it has and the amount of steps it takes to complete. We compare the two to get our runtime.

Is Big O an algorithm?

Big O Notation is a way to measure an algorithm's efficiency. It measures the time it takes to run your function as the input grows. Or in other words, how well does the function scale. There are two parts to measuring efficiency — time complexity and space complexity.


1 Answers

It would be O(M*(N-M)), where N is the number of elements in the sequence 1, and M is the number of elements in the sequence 2.

like image 88
Sergey Kalinichenko Avatar answered Sep 20 '22 09:09

Sergey Kalinichenko