equal
deleted
inserted
replaced
490 proof (induction n rule: fib.induct) |
490 proof (induction n rule: fib.induct) |
491 case (3 n) |
491 case (3 n) |
492 thus ?case using assms by (cases n) (auto simp: eval_nat_numeral) |
492 thus ?case using assms by (cases n) (auto simp: eval_nat_numeral) |
493 qed (insert assms, auto) |
493 qed (insert assms, auto) |
494 |
494 |
495 text \<open>An exponential lower bound for @{const fib}:\<close> |
495 text \<open>An exponential lower bound for \<^const>\<open>fib\<close>:\<close> |
496 |
496 |
497 lemma fib_lowerbound: |
497 lemma fib_lowerbound: |
498 defines "\<phi> \<equiv> (1 + sqrt 5) / 2" |
498 defines "\<phi> \<equiv> (1 + sqrt 5) / 2" |
499 defines "c \<equiv> 1 / \<phi> ^ 2" |
499 defines "c \<equiv> 1 / \<phi> ^ 2" |
500 assumes "n > 0" |
500 assumes "n > 0" |
532 also have "\<dots> \<le> size1 t" |
532 also have "\<dots> \<le> size1 t" |
533 using avl_fib_bound[of t "height t"] assms by simp |
533 using avl_fib_bound[of t "height t"] assms by simp |
534 finally show ?thesis . |
534 finally show ?thesis . |
535 qed |
535 qed |
536 |
536 |
537 text \<open>The height of an AVL tree is most @{term "(1/log 2 \<phi>)"} \<open>\<approx> 1.44\<close> times worse |
537 text \<open>The height of an AVL tree is most \<^term>\<open>(1/log 2 \<phi>)\<close> \<open>\<approx> 1.44\<close> times worse |
538 than @{term "log 2 (size1 t)"}:\<close> |
538 than \<^term>\<open>log 2 (size1 t)\<close>:\<close> |
539 |
539 |
540 lemma avl_height_upperbound: |
540 lemma avl_height_upperbound: |
541 defines "\<phi> \<equiv> (1 + sqrt 5) / 2" |
541 defines "\<phi> \<equiv> (1 + sqrt 5) / 2" |
542 assumes "avl t" |
542 assumes "avl t" |
543 shows "height t \<le> (1/log 2 \<phi>) * log 2 (size1 t)" |
543 shows "height t \<le> (1/log 2 \<phi>) * log 2 (size1 t)" |