diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-26 19:44:29 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-26 19:44:29 -0600 |
| commit | 5cb4ce51804e8bc60fef6f3e33ceaee0f05bacc6 (patch) | |
| tree | 58a88d84a8d826ae89a23d95d74404a1741bd3ba /src/03/08 | |
| parent | c93020800e852b17f4cf30fb867bccac88d61cbd (diff) | |
Collapse all questions into a single README
Diffstat (limited to 'src/03/08')
| -rw-r--r-- | src/03/08/README.md | 23 |
1 files changed, 0 insertions, 23 deletions
diff --git a/src/03/08/README.md b/src/03/08/README.md deleted file mode 100644 index 3cf319c..0000000 --- a/src/03/08/README.md +++ /dev/null @@ -1,23 +0,0 @@ -Prove that a binary tree with `k` leaves has height at least `log k`. - -The proof can be derived with the following. -Suppose we have a function `h` that takes input `k` -and returns a tree with `k` leaves. - -For each positive natural number we can -assert that the height of the tree must greater -than or equal to `log2(k)`. - -```plaintext -for each positive natural number - assert(height(h(k)) >= log2(k)) -``` - -An example test is provided in `btree_test.c` that -asserts that this holds true for the first -500 positive integers. - -```c -for (int k = 0; k < 500; ++k) - assert_that(btree_height(btree_generate(k)) >= log2(k), is_equal_to(true)); -``` |
