What Is the Efficiency of Combining Different Algorithm Complexities?

  • Thread starter surfy2455
  • Start date
  • Tags
    Algorithms
In summary, an algorithm is a set of rules followed to solve a problem. A combined algorithm is a combination of multiple algorithms that work together to solve a problem. It can be more efficient and effective than a single algorithm. The choice of algorithms to combine depends on the problem and their strengths. A common example is the A* algorithm, which combines Dijkstra's algorithm and heuristic search algorithms to find the shortest path on a graph.
  • #1
surfy2455
3
0
*solved

Homework Statement



Lets say we have three algorithms, which include the following complexities 200n, 3n^2, 2^n-1. What would be a combined algorithm which is efficient?

Homework Equations


The Attempt at a Solution



Let me know if I'm on the right path here.

100n+3n^2 + 2^(n-1)
=log(100n)+log(3n^2)+log(2^(n-1))
=[log(100) + log(n)]+[log(3)+log(n^2)]+[(n-1)*log(2)]
=[log(100) + log(n)]+log(n^2)+(n-1),exclude constants
=log(n)+2log(n)+n
=(3log(n)+n)

The efficiency of the combined algorithm is O(3log(n)).
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
surfy2455 said:

Homework Statement



Lets say we have three algorithms, which include the following complexities 200n, 3n^2, 2^n-1. What would be a combined algorithm which is efficient?

Homework Equations





The Attempt at a Solution



Let me know if I'm on the right path here.

100n+3n^2 + 2^(n-1)
=log(100n)+log(3n^2)+log(2^(n-1))
=[log(100) + log(n)]+[log(3)+log(n^2)]+[(n-1)*log(2)]
=[log(100) + log(n)]+log(n^2)+(n-1),exclude constants
=log(n)+2log(n)+n
=(3log(n)+n)

The efficiency of the combined algorithm is O(3log(n)).

I'm not sure about the logic behind your derivation. Adding together the Orders of different algorithms doesn't make sense to me. Also, in the second line, why have you taken term-by-term logs? The second line won't equal the first.

I could be wrong, but when I look at the problem as stated I imagine that the idea would be to have the program select, based upon the value of n, the algorithm which would minimize the run time. Then you would have different complexities for different ranges of n. The problem would then be to work out the ranges of n that suit each algorithm.
 
  • #3
gneill said:
I could be wrong, but when I look at the problem as stated I imagine that the idea would be to have the program select, based upon the value of n, the algorithm which would minimize the run time.

I think it is asking for what values of N is Alg(X) the fastest.

Naively, for what values of n (n>=0) is alg(1) < alg(2), alg(2)<alg(1), alg(2)<alg(3), alg (3)<alg(2), alg(3)<alg(1), alg(1)<alg3).
Then just select the best minima.

Starting with, for what vales of n does 200n - 3n^2 = 0
 
  • #4
surfy2455 said:
*solved

thread can be deleted.

We don't ordinarily delete the contents of threads when they're solved. Other people can sometimes benefit from them.
 
  • #5
This is because logarithmic functions grow at a slower rate compared to polynomial and exponential functions. By combining these algorithms, we have reduced the overall complexity to a more efficient and manageable level. However, it is important to note that the efficiency of an algorithm also depends on the specific input values and the implementation of the algorithm. Therefore, further analysis and testing may be necessary to determine the true efficiency of the combined algorithm.
 

FAQ: What Is the Efficiency of Combining Different Algorithm Complexities?

What is an algorithm?

An algorithm is a step-by-step procedure or set of rules that are followed to solve a problem or complete a task.

What is a combined algorithm?

A combined algorithm is a combination of multiple algorithms that work together to solve a problem or complete a task.

Why would you use a combined algorithm?

A combined algorithm can be more efficient and effective than a single algorithm, as it takes advantage of the strengths of each individual algorithm.

How do you choose which algorithms to combine?

The choice of algorithms to combine depends on the problem at hand and the strengths of each individual algorithm. It is important to select algorithms that complement each other and can work together to solve the problem.

Can you provide an example of a combined algorithm?

Yes, a common example of a combined algorithm is the A* algorithm, which combines elements of both Dijkstra's algorithm and heuristic search algorithms to find the shortest path between two points on a graph.

Back
Top