What Is the Efficiency of Combining Different Algorithm Complexities?

[surfy2455]

*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)).

 

[gneill]

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.

 

[Devils]

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

 

[Mark44]

*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.