|
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.
|
|
|
|
|
response below
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.
|
|
|
|
|
response below your entry
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.
|
|
|
|
|
Yes this is better, this is why I asked him what T(1) was, and he said "take a constant as C>0", which significantly changes the result
|
|
|
|
|
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.
|
|
|
|
|
|
It's ugly, ugly, ugly....
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Hi,
Is it possible to use Bug-1 algorithm without knowing the distance to the target ?
In every place (a matrix) I just know the way to this (N, NE, E, SE..), but not the distance.
modified on Tuesday, November 3, 2009 5:00 PM
|
|
|
|
|
If you now the direction from two points and the distance between them, then it's pretty simple trig to work out the distance to the third; Triangulation[^]
Panic, Chaos, Destruction.
My work here is done.
|
|
|
|
|
I need to make a divide&conquer algorithm for finding the dominant element in an array (dominant element = element which exists at least n/2 times in an array within the size n) . All you can do between those elements is compare them (no < relation or > relation) .
And also I need an algorithm which does it in O(n) (doesn't have to be d&c)
Thanks ahead for any help...
|
|
|
|
|
Well, this may not win any awards for style, but have you considered just using a hash table to aggregate the count?
It would be O(n) to hash everything, since I believe hash tables are theoretically in constant time... Then a subsequent O(n) to find the largest value in the hash table.
There's probably a more clever way to do it, but that would get the job done.
|
|
|
|
|
in the name of god
hello
if i know your question true you can do:
1-for i=0 n
B[A[i]]++;
for counting the number of repeating of them.
and then searching for max with O(n);
valhamdolelah.
|
|
|
|
|
That only works if you know the number range... What if the numbers are completely unknown, and can be as high as 2^16... Are you going to have an array that large?
|
|
|
|
|
khomeyni wrote: in the name of god
hello
Are you really in the US as your profile says? And if so, do you talk like this on the job?
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
no i cant yet change it i am from Iran i will change it soon and also yes we talk like this on job but not as this intensity 
|
|
|
|
|
Tim Craig wrote: Are you really in the US as your profile says? And if so, do you talk like this on the job?
I dont find anythin wrong in the way he speaks...
|
|
|
|
|
For the location stated in your profile, you probably wouldn't. Where I am, it would be considered highly unusual.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Hmmm... Strange... 
|
|
|
|
|
I think you need to get out and about and see how the rest of the world lives if you think that is strange.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
I do very well knw wats happening around... but it is offcourse strange wen u look at people and feel uncomfortable wen they spk abt their god or religion.. first stop discriminating people by religion or by any other means jst think and behave thet we al are civilised humans rather than looking at religion and stuff.. v guys are on 21st century  ...
|
|
|
|
|
Well, where this conversation is going, it should probably be move to the Back Room. However, since this thread is so old, I doubt anyone other than you and I are stirring up the dust here.
Do you really think work is the place to discuss religion? I supppose you think it's ok to be asked about your religion when applying for job then? Do you think that developing a regular speech pattern that immediately identifies outsiders to your religious bent is ignoring religion? How can I ignore it if you're talking about it all the time? I quit paying any attention to religion over 50 years ago. But it's hard to ignore those who continually try to ram it down my throat.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
