Q1. What would be the time complexity to find intersection of two **SORTED** ranges or arrays?

Which data structure or STL container would give the best time complexity?

Q2. Does O(n^{2} * log©) pass in 2 seconds time limit? n = 10^5

Q1. What would be the time complexity to find intersection of two **SORTED** ranges or arrays?

Which data structure or STL container would give the best time complexity?

Q2. Does O(n^{2} * log©) pass in 2 seconds time limit? n = 10^5

1 Like

Heya!

**For your first question**, you can use a simple function included in STL. [set_intersection][1] will do the work. You just need two vectors and then sort them and then use this function right away! I wonder how much easy it is to do all these things anyways.

**Approach2:**

There are many other ways to do this thing. You can use simple hashing or map for the same. Just have a count of the frequency of element in both the arrays and see if any element appears more than once.

**Now for your second query**, **It depends**. It depends on your program and the constant factors but anyway on a normal judge, we assume that 10^6 operations can be done under a second to be on the safer side always. If you just run a for loop 10^8 times without anything inside it then it can run in under a second sometimes but other operations like modulo,division are costly but here you are off by a large number. As you have not specified what is **c** I will try to neglect it and then you have an upper bound of O(10^10) which is like 1000 times 10^6 so it will run for around 16 minutes which is clearly not good.

Feel free to ask something more!

[1]: http://en.cppreference.com/w/cpp/algorithm/set_intersection

1 Like

Computer science is a very vast topic,wedding photography abu dhabi and like this article so much.Programs are neede in this field and it is very good.