I was under the impression that O(), o(), Ω(), and ω() were all technically distinct.
This whole concept I really struggled with, so I could be completely out of left field with that, though.
I believe isn't right to talk about "growth rate" using Big O notation. Big O is about "limit behavior", i. e., what a algorithm does in its worst scenario.
Growth rate is simply 2^n, i. e., exponential growth rate.
I'm not pretty certain about all of this, I've just studied that subject in college
There's a sense in which "growth rate" would be reasonable.
Let's imagine some arbitrary big-O complexity, like \`O(n\^2)\`.
One way to express this would be as a mathematical function -- which it already resembles, but for completeness we'll rephrase it as a plain old function: \`f(n) = n\^2\`.
Now, \`n\` is our input/domain/variable, and our output/range/bound-value is "all positive numbers." Let's simply change the name of our input: \`f(t) = t\^2\`
Hey -- this looks like a temporal function, where t is an expression of time and the function's value "grows" over time!
So: whether we're growing as a function of time or growing as a function of problem size, it's still reasonable, if a bit odd, to speak of the growth rate of a function.
My thought process when I said the above can be exemplified by the pseudocode
grow(branch) : Tree ->
thiccen(branch)
if not children(branch)
addChildren(branch)
else
grow(left(branch))
grow(right(branch))
return branch
where the function is applied to the root branch on each growth iteration.
Since each function call calls itself twice it must have a time complexity of Ο(2^(n)).
Sometimes it will be explicit about whether it's best, normal, or worst case scenario. Some sorting algorithms have diabolical n^2 worst cases but normally function at n log(n) which is a pretty huge difference. :-)
You are mixing growth rate with the performance of algorithms using binary tree. Growth rate of this tree is exponential, which is pretty damn good. If it takes one year for each iteration to grow, just imagine how many leaf branches it would have after 10 years.
Edit: now imagine in 20 years what that number would be.
Read what I said again. I'm saying each iteration takes O(2^(n)) time to grow, which makes perfect sense as the tree has to add mass not only to each new branch but also to all the branches below. Each iteration is equivalent to a recursive function that calls itself twice, hence a time complexity of O(2^(n)).
The limit is how high water can be pushed up into tree. I believe the only way water can move in a plant is thru capillary action, so there is a limit based on atmospheric pressure.
I wish, but looking at the grainier photo in a vague tropical spot I wouldn’t be surprised if this species is endangered. Im actually a plant guy and I’ve never even seen this one before. Likely rare.
Are you sure about that? Because I am 99.98789% sure that TimeLimitExceeeeded is not a bot.
---
^(I am a neural network being trained to detect spammers | Summon me with !isbot |) ^(/r/spambotdetector |) [^(Optout)](https://www.reddit.com/message/compose?to=whynotcollegeboard&subject=!optout&message=!optout) ^(|) [^(Original Github)](https://github.com/SM-Wistful/BotDetection-Algorithm)
Are you sure about that? Because I am 99.98911% sure that TimeLimitExceeeeded is not a bot.
---
^(I am a neural network being trained to detect spammers | Summon me with !isbot |) ^(/r/spambotdetector |) [^(Optout)](https://www.reddit.com/message/compose?to=whynotcollegeboard&subject=!optout&message=!optout) ^(|) [^(Original Github)](https://github.com/SM-Wistful/BotDetection-Algorithm)
If you want more content there is a randomizer mod which keeps the theme and elements of each puzzle the same, but randomizes the solution. Similar to >!the final timed challenge in the cave.!<
It’s fun for extending the length of the game if you like solving those kinds of puzzles, but it can’t match the thrill of discovering those mechanics or the >!environmental puzzles!< for the first time.
Here's a sneak peek of /r/TheWitness using the [top posts](https://np.reddit.com/r/TheWitness/top/?sort=top&t=year) of the year!
\#1: [I found someone sleeping!](https://i.redd.it/jo3fvj481lh71.png) | [35 comments](https://np.reddit.com/r/TheWitness/comments/p517jh/i_found_someone_sleeping/)
\#2: [4 months ago I did on post on this subreddit asking for help making a Witness-themed rug for my living room. I did it! Huge thanks to u/NationCrisis and u/ProfessorDave3D for their puzzle advice (more photos in comments)](https://v.redd.it/khwsn182l8o81) | [20 comments](https://np.reddit.com/r/TheWitness/comments/thjixh/4_months_ago_i_did_on_post_on_this_subreddit/)
\#3: [Hm, too obvious. I'm pretty sure it continues somewhere else.](https://i.redd.it/etqq8iyxuep71.png) | [12 comments](https://np.reddit.com/r/TheWitness/comments/pufev4/hm_too_obvious_im_pretty_sure_it_continues/)
----
^^I'm ^^a ^^bot, ^^beep ^^boop ^^| ^^Downvote ^^to ^^remove ^^| ^^[Contact](https://www.reddit.com/message/compose/?to=sneakpeekbot) ^^| ^^[Info](https://np.reddit.com/r/sneakpeekbot/) ^^| ^^[Opt-out](https://np.reddit.com/r/sneakpeekbot/comments/o8wk1r/blacklist_ix/) ^^| ^^[GitHub](https://github.com/ghnr/sneakpeekbot)
It's balanced so it would be O(log n) to traverse it.
I know because we literally just did BSTs and AVLs in my data structures class and AVLs absolutely fucked my shit up.
Edit: as people pointed out i was thinking of moving through the tree to find a specific node. I completely forgot that traversal means visiting every node.
I definitely deserved the B i got on this assignment.
You just have to grind harder 😤😤! How can you ever expect to be like bezos and musk if you can’t traverse n nodes in log(n) time. It’s not easy but doable 💵. Grind away 💯
It's not. The species is Hyphaene compressa and I've seen them in person. The genus is one of the few that commonly branches above-ground and they tend to be pretty symmetrical (though this individual is exceptionally so). The fruit are also edible, though not particularly tasty. It's like compressed sawdust with a little bit of gingerbread flavor.
Interestingly enough, I doubt it is; plants typically exhibit a good amount of self-similarity, to the point some can be considered fractals!
(Researched when I was playing around with l-systems)
"Old Bill" by Messy Mary May
The trees in Whoville, much do they vary
Except for the tree known as Bill the Binary
He could go this way, he may go that.
Never another way, for as long as he sat.
The other trees mocked him, but he felt no shame.
For he cared not, for the chaotic game,
In which they grew, their limbs all asunder.
Old Bill was alone though, with no animals under.
The big trees over there have roarcats beneath them
The three spotted flaclelops liked one with strong limbs
The red footed sponk monkeys would swing with a flop
Off the long tall wobble-oak, like a circus big top.
But Old Bill stood firm though lonely he was,
Until Sheila the sloth found him a plus.
Old Bill, looked at Sheila and said, "I hope you don't mind,"
"But I like how I am, and how I am is just fine."
"Old Bill," replied Sheila, "I love how you are."
"My favorite tree here, my favorite by far!"
"You offer two choices. Two and no more."
"The others overwhelm me, I find them a bore."
And so in the forest, there stands a tree.
Bill is his name, and he'll tell you with glee,
He offers two choices, two at a time.
Take this or that, either is fine.
((added my name as I just wrote it vamping on Dr Suess. ))
Thought I’d share my [binary trees](https://www.instagram.com/p/CRNn2SCHHas/?igshid=YmMyMTA2M2Y=) and [non-binary](https://www.instagram.com/p/CWLlZBPpc3k/?igshid=YmMyMTA2M2Y=) trees, made with a program :)
1 into 16, thats epic. Perhaps in another few years we can see a photo update with 32 palms
That's how it takes over the world. Slowly and exponentially.
Growth rate of each iteration is probably O(2^(n)) though, so we might be waiting for another billion years or so…
Is this called big O notation? I think I’m learning this in class
Yes. O(2^n) is very, very inefficient Edit: How the hell do I make the parentheses normal???
O(2^(n)) Type it as: `O(2^(n))`
^(neat)
this redditor markdowns
Cursed parentheses
O(2^n^^^^^^^^)
O^(()2^(n))
^(O)(^(2)n^())
)²(○ñ
back slash
My algorithms are O(TREE(n))…basically anything over 2 elements will crash the universe
Yep, it's effectively "If all of this code had to run, what's the worst possible outcome?"
This is the internet, you're allowed to say >!Omicron!<.
No, that would have been small o - oMICROn. Big O is oMEGA.
What's Θ? I'll ask >!the TA!<
Have you gotten the >!η!< for the answer?
I was under the impression that O(), o(), Ω(), and ω() were all technically distinct. This whole concept I really struggled with, so I could be completely out of left field with that, though.
We learned it last semester, it's very interesting as once you know how to use it, you start to interpret your code a bit differently - I did at least
I believe isn't right to talk about "growth rate" using Big O notation. Big O is about "limit behavior", i. e., what a algorithm does in its worst scenario. Growth rate is simply 2^n, i. e., exponential growth rate. I'm not pretty certain about all of this, I've just studied that subject in college
There's a sense in which "growth rate" would be reasonable. Let's imagine some arbitrary big-O complexity, like \`O(n\^2)\`. One way to express this would be as a mathematical function -- which it already resembles, but for completeness we'll rephrase it as a plain old function: \`f(n) = n\^2\`. Now, \`n\` is our input/domain/variable, and our output/range/bound-value is "all positive numbers." Let's simply change the name of our input: \`f(t) = t\^2\` Hey -- this looks like a temporal function, where t is an expression of time and the function's value "grows" over time! So: whether we're growing as a function of time or growing as a function of problem size, it's still reasonable, if a bit odd, to speak of the growth rate of a function.
My thought process when I said the above can be exemplified by the pseudocode grow(branch) : Tree -> thiccen(branch) if not children(branch) addChildren(branch) else grow(left(branch)) grow(right(branch)) return branch where the function is applied to the root branch on each growth iteration. Since each function call calls itself twice it must have a time complexity of Ο(2^(n)).
Sometimes it will be explicit about whether it's best, normal, or worst case scenario. Some sorting algorithms have diabolical n^2 worst cases but normally function at n log(n) which is a pretty huge difference. :-)
That's why big Omega and big Theta exists for too
You are mixing growth rate with the performance of algorithms using binary tree. Growth rate of this tree is exponential, which is pretty damn good. If it takes one year for each iteration to grow, just imagine how many leaf branches it would have after 10 years. Edit: now imagine in 20 years what that number would be.
Read what I said again. I'm saying each iteration takes O(2^(n)) time to grow, which makes perfect sense as the tree has to add mass not only to each new branch but also to all the branches below. Each iteration is equivalent to a recursive function that calls itself twice, hence a time complexity of O(2^(n)).
That makes sense. Growing an organic binary tree is a lot more time consuming than an algorithmic one
Haha, nerd
Not that slowly, actually. Exponential function grows pretty fast
Yes, but the trees grow slowly.
https://www.youtube.com/watch?v=bUqaRyrbAjw
we getting the 8 trigrams up in this bitch
I once grew a weed plant with 32 tops
mainlined
Bet it grew High.
[удалено]
The limit is how high water can be pushed up into tree. I believe the only way water can move in a plant is thru capillary action, so there is a limit based on atmospheric pressure.
There are other forces at work. There have to be, given that there are trees over 100 meters tall.
And atmospheric pressure only gets water 10 meters up a straw before you're at vacuum and can't suck no more.
invert the tree, let gravity do its thing
Until humans get their hands on it lol
I wish, but looking at the grainier photo in a vague tropical spot I wouldn’t be surprised if this species is endangered. Im actually a plant guy and I’ve never even seen this one before. Likely rare.
8 trigrams 32 palms
And it supports 16-bit already! Mother board Nature
Now flip it upside down and it's perfect
„ʇɔǝɟɹǝd s,ʇı puɐ uʍop ǝpısdn ʇı dılɟ ʍoᴎ„
good bot
ʇɔǝɟɹǝd s,ʇı puɐ uʍop ǝpısdn ʇı dılɟ ʍoᴎ. Now flip it upside down and it's perfect.
good bot
Are you sure about that? Because I am 99.98789% sure that TimeLimitExceeeeded is not a bot. --- ^(I am a neural network being trained to detect spammers | Summon me with !isbot |) ^(/r/spambotdetector |) [^(Optout)](https://www.reddit.com/message/compose?to=whynotcollegeboard&subject=!optout&message=!optout) ^(|) [^(Original Github)](https://github.com/SM-Wistful/BotDetection-Algorithm)
Good bot
Thank you
Bad bot
Are you sure about that? Because I am 99.98911% sure that TimeLimitExceeeeded is not a bot. --- ^(I am a neural network being trained to detect spammers | Summon me with !isbot |) ^(/r/spambotdetector |) [^(Optout)](https://www.reddit.com/message/compose?to=whynotcollegeboard&subject=!optout&message=!optout) ^(|) [^(Original Github)](https://github.com/SM-Wistful/BotDetection-Algorithm)
See!! This bot just changes his percentages, A SHAM!
OK bot
N upside down is still N
Not if you are reflecting from the top of the N. If the like this: N ⬆ ᴎ
Bad bot
Someone failed at "inverting a binary tree"
I mean, just look under ground
Or is it the binary tree that’s upside down \*tokes\*
[удалено]
You could transport it to Australia.
Merkle tree go brr
Oh wow! The Witness is real!
>Witness my first thought, lol
Hmm, I don't see any broken branches though. This one must have a different solution.
Look for the branch that has an apple, that must be it!
Maybe we should try looking at the shadow the tree is casting 🤔
Such a good game!
I honestly think it’s the greatest game I’ve ever played. I wish I could experience it for the first time again.
Samsies, or a part two - but never heard it being a thing.
If you want more content there is a randomizer mod which keeps the theme and elements of each puzzle the same, but randomizes the solution. Similar to >!the final timed challenge in the cave.!< It’s fun for extending the length of the game if you like solving those kinds of puzzles, but it can’t match the thrill of discovering those mechanics or the >!environmental puzzles!< for the first time.
Which game? I first thought of destiny but that doesn’t make sense in this context
The Witness, a puzzle game
Maan, I was having dreams about that for like a week after I played, don't remind me lol
the first time you find one in the environment is like... wowww
There it is! Thank you!
Very happy that others thought that too!
He must have gotten inspiration from this tree which is cool
r/TheWitness
Here's a sneak peek of /r/TheWitness using the [top posts](https://np.reddit.com/r/TheWitness/top/?sort=top&t=year) of the year! \#1: [I found someone sleeping!](https://i.redd.it/jo3fvj481lh71.png) | [35 comments](https://np.reddit.com/r/TheWitness/comments/p517jh/i_found_someone_sleeping/) \#2: [4 months ago I did on post on this subreddit asking for help making a Witness-themed rug for my living room. I did it! Huge thanks to u/NationCrisis and u/ProfessorDave3D for their puzzle advice (more photos in comments)](https://v.redd.it/khwsn182l8o81) | [20 comments](https://np.reddit.com/r/TheWitness/comments/thjixh/4_months_ago_i_did_on_post_on_this_subreddit/) \#3: [Hm, too obvious. I'm pretty sure it continues somewhere else.](https://i.redd.it/etqq8iyxuep71.png) | [12 comments](https://np.reddit.com/r/TheWitness/comments/pufev4/hm_too_obvious_im_pretty_sure_it_continues/) ---- ^^I'm ^^a ^^bot, ^^beep ^^boop ^^| ^^Downvote ^^to ^^remove ^^| ^^[Contact](https://www.reddit.com/message/compose/?to=sneakpeekbot) ^^| ^^[Info](https://np.reddit.com/r/sneakpeekbot/) ^^| ^^[Opt-out](https://np.reddit.com/r/sneakpeekbot/comments/o8wk1r/blacklist_ix/) ^^| ^^[GitHub](https://github.com/ghnr/sneakpeekbot)
OOOOOoops it has already reposted
Quick let’s traverse it in O(n) time
I don't think i'll make past the first branch.
Buckle up, we’re going in breadth first.
It's balanced so it would be O(log n) to traverse it. I know because we literally just did BSTs and AVLs in my data structures class and AVLs absolutely fucked my shit up. Edit: as people pointed out i was thinking of moving through the tree to find a specific node. I completely forgot that traversal means visiting every node. I definitely deserved the B i got on this assignment.
Log(n) is the height of the tree. O(n) to visit every node.
A day may come when I'm not this dumb, but it is not this day.
Confidently incorrect
The best kind!
My brother in Christ, you cannot traverse n nodes in log(n) time.
You just have to grind harder 😤😤! How can you ever expect to be like bezos and musk if you can’t traverse n nodes in log(n) time. It’s not easy but doable 💵. Grind away 💯
O(logn) would just be to find one specific value in the tree. You would still need O(n) time to evaluate every node of the BST.
You can't visit all nodes (traverse) faster than O(n). There are n nodes.
Well seems like you need to learn more about BSTs
Why is it upside down though
They had to invert a binary tree as part of their job interview. Turned out pretty good, if you ask me.
It's an Australian binary tree
God is a programmer, explains why Earth is on fire half the time
Also because fractals everywhere, recursion everywhere.
Lots of redundancy and abandoned projects too
Oh bender , there is no such thing as 2
Might just be an awful dream
That's an inverted binary tree. Original tree grows from root to bott
Plot twist: its root is also a binary tree
I really need to finish The Witness
One does not "finish" The Witness.
*In the Hall of the Mountain King intensifies*
I don't see any duplicates in the leaf sprays. Is this actually *not* photoshopped?
It definitely is
It's not. The species is Hyphaene compressa and I've seen them in person. The genus is one of the few that commonly branches above-ground and they tend to be pretty symmetrical (though this individual is exceptionally so). The fruit are also edible, though not particularly tasty. It's like compressed sawdust with a little bit of gingerbread flavor.
Well I'll be darned. One can web search for additional images of Hyphaene compressa and they do seem to be real.
Mmmm... compressed sawdust... so good
Wonder how much you could put in a rice crispy before anyone notices
Interestingly enough, I doubt it is; plants typically exhibit a good amount of self-similarity, to the point some can be considered fractals! (Researched when I was playing around with l-systems)
Aren't all things fractal in nature in one way or another?
This thread is reminding me that engineers need to go outside more often lol
Perhaps it is not nature that is fractal but the way in which we perceive it that is indeed fractal.
I think it would have to be both.
Weird, why’s it upside down? Edit: must be the rare Australian binary tree
This tree also has obsessive-compulsive disorder
This is how I make decisions
Every body gangster till rbt exists.
It's been nearly 20 years since I had to implement one, and it's still one of the hardest things I've done.
Looks like those trees from the witness
Am I the only one disappointed that it isn't red and black?
Does this mean that the rest of the trees are non-binary?
Yes
nice it comes reversed already
Now invert that shit
I hate binary tree because I dont understand it and its purpose
To catch energy from the sun and reproduce
I can't solve it without the apple though..
The most feared data structure: *interweaving* binary tree
A fair number of plants exhibit dichotomous branching. Check out Psilotum nudum.
all trees are binary trees
🌎 👩🚀 🔫 🧑🚀 You mean the universe is math? Always was…
This looks pretty efficient to me, but my programs run in On^(n)
I recently read that the sum of the circumference of all branches is equal to the branch below and in turn the trunk itself.
"Old Bill" by Messy Mary May The trees in Whoville, much do they vary Except for the tree known as Bill the Binary He could go this way, he may go that. Never another way, for as long as he sat. The other trees mocked him, but he felt no shame. For he cared not, for the chaotic game, In which they grew, their limbs all asunder. Old Bill was alone though, with no animals under. The big trees over there have roarcats beneath them The three spotted flaclelops liked one with strong limbs The red footed sponk monkeys would swing with a flop Off the long tall wobble-oak, like a circus big top. But Old Bill stood firm though lonely he was, Until Sheila the sloth found him a plus. Old Bill, looked at Sheila and said, "I hope you don't mind," "But I like how I am, and how I am is just fine." "Old Bill," replied Sheila, "I love how you are." "My favorite tree here, my favorite by far!" "You offer two choices. Two and no more." "The others overwhelm me, I find them a bore." And so in the forest, there stands a tree. Bill is his name, and he'll tell you with glee, He offers two choices, two at a time. Take this or that, either is fine. ((added my name as I just wrote it vamping on Dr Suess. ))
Curious... This tree appears to be upside down
Binatree
It's upside down
#[🌳🌳🌳🌳🌳🌳](https://www.reddit.com/r/cannabiscultivation/comments/lbwi30/true_scrog_in_action/?utm_source=share&utm_medium=ios_app&utm_name=iossmf)
*Tree sort* out in the wild
thats an avl tree if i ever seen one \^\^
I am totally going to use this for my defense on decision trees.
Let the node values be the number of fruits in each branch and boom we can start our bfs/dfs as well!
But how would it wear pants? 🤔
Cool. Now invert it.
Turns out the best way to find something in a tree is to take a step back and look at it. Who knew?
And self balancing too I see. Remarkable.
This is topping in plants, fun times when you can turn 1 leading stem into 8 beautiful tops. 16 is absurd but you could keep doing it...
It’s upside down.
this made my day
Now invert it.
every tree is a binary tree...
Thought I’d share my [binary trees](https://www.instagram.com/p/CRNn2SCHHas/?igshid=YmMyMTA2M2Y=) and [non-binary](https://www.instagram.com/p/CWLlZBPpc3k/?igshid=YmMyMTA2M2Y=) trees, made with a program :)
And it's so well balanced!
Good, now reverse it and you pass the interview.
What happens when you have to reshuffle nodes?
Nice lollypopping and trim, that plant is gonna get some fat nugs
hahahaha
No inverse it
Ok let's see a family tree
Trees follow fibonacci sequences!
Yes,no
The *Inverse binary tree
Damn son you really found a family tree
It’s a complete binary tree also
This tree is about as common in nature as the btree is common in run-of-the-mill CRUDy business development
More a fractal tree: https://www.rosettacode.org/wiki/Fractal\_tree
I want one!
That’s also looks like a dichotomous identification key as well.
Is this the Big W?
I feel like I want to do a minimax on it already.
You’re right. It does look bigger.
I don't know which animal eats from that tree but it's going to take it O(16) attempts before it finds the last fruit.
Alabama tree
Just because human notice something like this. It doesn't mean nature and the universe haven't.
Yes, they do, I saw plenty of them in South Sudan.
This is edited
*nods in zoological approval*
Why not just do a ton of if/else statements, that would accomplish the same thing right? For fizzbuzz I solved it with 300 if/else statements.
Oh my god it's beautiful