algorithmtime-complexitycomplexity-theory# For a certain problem if I have a O(f1(m,n)) algorithm and a O(f2(m,n)) algorithm, can I have a O(min(f1(m,n),f2(m,n))) algorithm?

Actually, I have this question because of clrs 14.3.4 https://walkccc.me/CLRS/Chap14/14.3/ I know how to prove O(N)for traversal and O(k*logN) for delete every time. so how to prove there exists O(min(N,k*logN)) becomes a question. (I asked it in How to prove the time complexity of query in interval tree)

Assert this is correct, can any algorithms having a O(f1(m,n)) and a O(f2(m,n)) solution have a O(min(f1(m,n),f2(m,n))) solution(for m,n not known before execution).

Solution

Yes. If you have a O(f1(m,n)) and a O(f2(m,n)) solution, you could execute each of the solutions in pseudo-parallel (time-sliceing) and stop when one of them found the solution.

This way you get an O(min(f1(m,n),f2(m,n))) algorithm.

This is 2 times slower than performing the algorithm that found the solution first alone but that makes no difference according to the O-Notation (because 2 is only a constant factor).

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array