order of algorithm
-
In the end, he does want the answer, but he is more interested in how you come up with the answer - the way to solve it. In effect, he does not want you to do his homework for him, he wants to know HOW to do his homework. That is unusual for this kind of question, and I think he deserves kudos! Unfortunately, I don't know how to solve it.
Silver member by constant and unflinching longevity.
-
in the name of god hello how can we solve this problem to find the order of it: T(n)=sqrt(n)*(T(sqrt(n))+n order =? valhamdolelah.
Thank you for wanting to know HOW, not just wanting the answer. . Are you solving for the computational order of an algorithm that takes this long to process (the Big O notation), or are you looking for a numerical order of magnitude for the result of applying this equation to an arbitrary value 'n' ( eg. T(2) = sqrt(2)+T(sqrt(2))+2)? . T(n)=sqrt(n)*(T(sqrt(n))+n . The Big O would be O(n). the two terms are added together, so each term can be taken by itself. sqrt(n) * T(sqrt(n))becomes 'n' in the limit, so you have two O(n) terms, which is the same as O(n). . If you are looking for numerics, I can't really help you.
Silver member by constant and unflinching longevity.
-
Thank you for wanting to know HOW, not just wanting the answer. . Are you solving for the computational order of an algorithm that takes this long to process (the Big O notation), or are you looking for a numerical order of magnitude for the result of applying this equation to an arbitrary value 'n' ( eg. T(2) = sqrt(2)+T(sqrt(2))+2)? . T(n)=sqrt(n)*(T(sqrt(n))+n . The Big O would be O(n). the two terms are added together, so each term can be taken by itself. sqrt(n) * T(sqrt(n))becomes 'n' in the limit, so you have two O(n) terms, which is the same as O(n). . If you are looking for numerics, I can't really help you.
Silver member by constant and unflinching longevity.
thanks very much for your attention i want to know the computational order of it as you said : sqrt(n) * T(sqrt(n))becomes 'n' in the limit, so you have two O(n) terms, which is the same as O(n). but why in limit it becomes n?,please explain more. also i think finding it as numerical would be interesting but i think this would be hard!!! thanks.
-
Thank you for wanting to know HOW, not just wanting the answer. . Are you solving for the computational order of an algorithm that takes this long to process (the Big O notation), or are you looking for a numerical order of magnitude for the result of applying this equation to an arbitrary value 'n' ( eg. T(2) = sqrt(2)+T(sqrt(2))+2)? . T(n)=sqrt(n)*(T(sqrt(n))+n . The Big O would be O(n). the two terms are added together, so each term can be taken by itself. sqrt(n) * T(sqrt(n))becomes 'n' in the limit, so you have two O(n) terms, which is the same as O(n). . If you are looking for numerics, I can't really help you.
Silver member by constant and unflinching longevity.
-
Thank you for wanting to know HOW, not just wanting the answer. . Are you solving for the computational order of an algorithm that takes this long to process (the Big O notation), or are you looking for a numerical order of magnitude for the result of applying this equation to an arbitrary value 'n' ( eg. T(2) = sqrt(2)+T(sqrt(2))+2)? . T(n)=sqrt(n)*(T(sqrt(n))+n . The Big O would be O(n). the two terms are added together, so each term can be taken by itself. sqrt(n) * T(sqrt(n))becomes 'n' in the limit, so you have two O(n) terms, which is the same as O(n). . If you are looking for numerics, I can't really help you.
Silver member by constant and unflinching longevity.
I'm answering both of you, so I am just tacking it on to the end. The problem in what I wrote was with the T(sqrt(n)) part of the function. The answer hinges on what F(n) = sqrt(n)*F(sqrt(n)) is. I was thinking it approached (n), but I see I was wrong, it may approach(n^1.5), which would mean it dominated. When you add in the (+ n), with an infinite recursion, I see that this goes to infinity, even for n = 1. As a matter of fact, I will kick my own but on this and say that, while I don't know which order of infinity this ends up being, but, since there is no stop condition on the recursion, the answer, even for n=1 is infinity, given this analysis: T(1) = 1*T(1)+1 which shows that you end up adding 1 at each recursion level, with an infinite number of recursions (no stop condition). And it just gets larger from there. khomeyni - sorry for my flawed analysis, thank you for asking why. harold aptroot - is that a better analysis? I'm asking, not being snide.
Silver member by constant and unflinching longevity.
-
I have to disagree. The two terms are not O(n) at all, one of them is O(n^0.5) which is asymptotically different from O(n), and the other is unknown until the recursion is solved.
-
thanks very much for your attention i want to know the computational order of it as you said : sqrt(n) * T(sqrt(n))becomes 'n' in the limit, so you have two O(n) terms, which is the same as O(n). but why in limit it becomes n?,please explain more. also i think finding it as numerical would be interesting but i think this would be hard!!! thanks.
-
I'm answering both of you, so I am just tacking it on to the end. The problem in what I wrote was with the T(sqrt(n)) part of the function. The answer hinges on what F(n) = sqrt(n)*F(sqrt(n)) is. I was thinking it approached (n), but I see I was wrong, it may approach(n^1.5), which would mean it dominated. When you add in the (+ n), with an infinite recursion, I see that this goes to infinity, even for n = 1. As a matter of fact, I will kick my own but on this and say that, while I don't know which order of infinity this ends up being, but, since there is no stop condition on the recursion, the answer, even for n=1 is infinity, given this analysis: T(1) = 1*T(1)+1 which shows that you end up adding 1 at each recursion level, with an infinite number of recursions (no stop condition). And it just gets larger from there. khomeyni - sorry for my flawed analysis, thank you for asking why. harold aptroot - is that a better analysis? I'm asking, not being snide.
Silver member by constant and unflinching longevity.
-
I'm answering both of you, so I am just tacking it on to the end. The problem in what I wrote was with the T(sqrt(n)) part of the function. The answer hinges on what F(n) = sqrt(n)*F(sqrt(n)) is. I was thinking it approached (n), but I see I was wrong, it may approach(n^1.5), which would mean it dominated. When you add in the (+ n), with an infinite recursion, I see that this goes to infinity, even for n = 1. As a matter of fact, I will kick my own but on this and say that, while I don't know which order of infinity this ends up being, but, since there is no stop condition on the recursion, the answer, even for n=1 is infinity, given this analysis: T(1) = 1*T(1)+1 which shows that you end up adding 1 at each recursion level, with an infinite number of recursions (no stop condition). And it just gets larger from there. khomeyni - sorry for my flawed analysis, thank you for asking why. harold aptroot - is that a better analysis? I'm asking, not being snide.
Silver member by constant and unflinching longevity.
thanks for your getting involved in it i say that we must take T(1) a constant as c so the stop condition is T(1),but i dont know how either you or harold aptroot solved this? you said that it would be n^1.5 how you find it? please explain more on the solution not only the final answer.if we only find a order it is enough. thanks. valhamdolelah.
-
thanks for your getting involved in it i say that we must take T(1) a constant as c so the stop condition is T(1),but i dont know how either you or harold aptroot solved this? you said that it would be n^1.5 how you find it? please explain more on the solution not only the final answer.if we only find a order it is enough. thanks. valhamdolelah.
khomeyni wrote:
you said that it would be n^1.5 how you find it?
I said that about t(n) = sqrt(n)+T(sqrt(n)),but waswrong on the overall analysis at that point. Than I went on to do the actual form t(n)=sqrt(n)+t(sqrt(n))+n and said it was infinite, though I don't know what order. Even if you remove the sqrt(n)part, t(n)=t(sqrt(n))+n, but assume t(1) is a stop condition,if you try t(n >1), sqrt(sqrt(sqrt(...(n)))) approaches, but never reaches 1, so you have and infinite series of summing for x = 1 to infinity of n^(1/x). Sums an infinite progression of numbers > 1.
Silver member by constant and unflinching longevity.