Timeline for Proving that a preorder traversal of a rooted tree can be performed in linear time
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2021 at 23:12 | comment | added | Hendrik Jan | It is actually hard to see what is really assumed about trees, and what is to prove here? Usually we show complexity results given a representation of the data structure (here nodes and edges). Then we reason about the number of steps it takes it takes to collect information or move to certain nodes via edges. Below, in the structural induction proof, I see none of these. | |
| Feb 26, 2021 at 8:29 | history | became hot network question | |||
| Feb 26, 2021 at 7:46 | comment | added | greybeard |
You may need assumptions such as getting from $T$ (or $r$) to any of the subtrees takes time bounded above by a constant. (You may be making this in does constant work on each visit.) It's too obvious suggest by contradiction, each by induction.
|
|
| Feb 26, 2021 at 0:39 | history | edited | Steven | CC BY-SA 4.0 |
edited title
|
| Feb 26, 2021 at 0:22 | answer | added | D.W.♦ | timeline score: 1 | |
| Feb 26, 2021 at 0:22 | vote | accept | tossimmar | ||
| Feb 26, 2021 at 0:19 | answer | added | Steven | timeline score: 2 | |
| Feb 26, 2021 at 0:15 | history | edited | tossimmar | CC BY-SA 4.0 |
added 68 characters in body
|
| Feb 26, 2021 at 0:10 | review | First posts | |||
| Feb 26, 2021 at 8:25 | |||||
| Feb 26, 2021 at 0:07 | history | asked | tossimmar | CC BY-SA 4.0 |