Comments (9)
"The other option is that x tends to 0, so our steps would be the biggest size possible (N), so we would do only one jump and then we would need to do a linear search of N elements ... again we end up with O(N)."
I almost fell for this interpretation as well because I thought there might be symmetry in the graph. It seems intuitive. However, the other option is specifically when x =1, not when x approaches 0. For N^(1/x) as x approaches 0 it is undefined. The right and left limit don't equal.
"My guess was that the optimal x value is found when both of these values are as close as possible:"
Your guess is correct, but you're missing some parts I think. You have to show why the optimal x value is when the functions are equal.
Here is a more concise reason why:
In general, if you have an increasing function on some interval f' and a decreasing function g' on that same interval then their intersection is the minimum of max(f',g') assuming they have a unique intersection (Here is a post showing why: https://math.stackexchange.com/questions/132974/minimizing-a-maximum). The explanation is a better, more formal, more generalizable version of my explanation for why x =2 is optimal in the previous post. It shows specifically why the intersection must be the minimum.
We can apply this concept here and look at the interval (0,infinity) on max(
Now the question is whether (-infinity, 0) contains a better x. I think this is just a matter of showing that
Thanks for bringing up the idea of there being a reason why the intersection is the minimum! I think that prespective makes showing the optimal minimum much clearer and allowed for a more generalized approach.
from kata-machine.
@jts307 sorry forgot to comment this:
https://www.geogebra.org/calculator/bmtut7hd
One function is constantly increasing and the other is constantly decreasing (considering only the positive side) so they will intersect only in one point.
I guess I can set this as "closed". Thanks a lot 🙌
from kata-machine.
For any integer x > 2, in
from kata-machine.
@aidoskanapyanov maybe I need a bigger explanation (probably because I am not good at math 🥴 sorry).
Why for any integer x > 2 in
And yes, if x tends to infinity (because
Probably we need to do something like:
☝️ which means that we should use the biggest x possible as long as our jumps are not jumps of 1 unit. But still ... this sounds wrong to me. Because that means that we are doing jumps of two units ... if we drop the constants we get O(N).
Probably there is another way to do or write this. Something like "x as big as possible while
Sorry if I am not clear, maths is not my thing; in this case, I don't know how to express myself better.
from kata-machine.
So,
There are two ways I think you can make sense of a runtime of O(n). The first way is that when x goes to infinity two things happen.
The other way is to think about the runtime of O(n) is the case where x=1. All a 1st root is if you think about is just N, so
Does this make sense?
from kata-machine.
This also might help:
from kata-machine.
The optimal value for x is 2. To find this formally, one could potentially minimize max(
My intuitive understanding of the optimal value of 2 is thinking about how when x=2, then
Using similiar logic, when 0 < x < 2,
You can extend this logic for the other parts of the graph, but I think the point is kind of clear.
from kata-machine.
@jts307 I was thinking about this and reached a similar conclusion:
Given
x tends to infinity so as you said our steps would be the smallest possible (steps of one unit) and we would end up with a linear search O(N).
The other option is that x tends to 0, so our steps would be the biggest size possible (N), so we would do only one jump and then we would need to do a linear search of N elements ... again we end up with O(N).
So I guess that the real question is how to find the optimal value for x.
Intuitively I was thinking that the best way to find this is the following:
My guess was that the optimal x value is found when both of these values are as close as possible:
☝️ this is (if I understood you properly) what you were referring by:
Now the question is whether
$\sqrt[x]{N}$ or$\sqrt[x]{N^{x-1}}$ is the term that dominates the runtime.
BTW, thanks for making explicit that:
It helped me understand, Its been quite a while since I've done some maths like these.
So by moving everything to the exponent, we can try to find the optimal value of x like this:
Now I might be doing a horrible mistake here, but I think we can remove N out of that equation:
☝️ reaching the same conclusion you did.
I am not sure if my math is correct 🥴 so I tried to be as clear as I could, if I made any mistake here please let me know.
from kata-machine.
@ajaralampidis No problem!
from kata-machine.
Related Issues (20)
- tail not getting set to undefined when queue.length === 1 in dequeue() function HOT 2
- Doubly Linked List implementation? HOT 1
- Derivation/Proof for square root of n in Two Crystal Ball problem
- Kata machine for Golang HOT 1
- Kata machine in Python HOT 1
- correct implementation of insertAt() is not checked, for doubly linked list
- My Merge Sort impl would not pass the test?
- Solutions
- npx jest Bubble test keeps on running HOT 2
- Compare Binary Trees BFS solution
- Is this a valid solution to the Two Crystal Balls problem? HOT 7
- Two Crystal balls failing for a custom test HOT 2
- No tests for insertAt for lists HOT 1
- Why not simplify TwoCrystalBalls to this? HOT 1
- BFS Graph Matrix bug?
- TwoCrystalBalls: Different appraoch HOT 3
- Off by one error in Two Crystal Ball Solution? HOT 1
- What about this implementation of pop() for Stack? HOT 1
- Shouldn't ring buffer test init ring buffer object with capacity as an argument?
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from kata-machine.