CSE 2321 Lecture 26: Lecture 26

5 views5 pages
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
Lecture 26
Iteration method for recurrences
decompose recurrance into aseries of
terms and derive the nth expression from
the previous ones
EX Binary Search half interval 1logarithmic search
constant time C
constant time Cz
cconstant time
Sameproblem
If Jaumepbum
of size 42
A112,3 4517,9 Il a8
X710 1hi 8
I23 57911 AEmidt A43 4
I2345678
mid hut 812J 14.5J 4
Amid A43 4
binary_search(A, lo, hi, x)
{
if (A[lo] > A[hi)
return false
mid = L(lo+hi)/2
if (x = A[mid])
return true
if (x < A[mid])
binary_search(A,lo,mid-1,x)
if (x > A[mid])
binary_search(A,mid+1,hi,x);
}!
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

Already have an account? Log in
I234509 11
I2345678
mid L582JL6.5J 6
Amid A63 7
Amid A67
X6
From the binarysearch alg above
1nCt THz
Find explicit formula ofTCD using
the iteration method
1nCtT nz1st iteration
Ct Ct TN4e2ND
Ct Ct Ct 1Chl83RD
CtT4240 4th
4times
be TKD
its sunning n2h then ktog n
cnclognTG
Thus Tbn 0Clog n
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.