- 00:00:00 hi guys in this video we're gonna go
- 00:00:02 through an example of solving
- 00:00:04 recurrences in this case we'll be
- 00:00:06 solving mergesort okay so just a recap
- 00:00:10 mergesort takes an array of size n and
- 00:00:13 breaks it into smaller and smaller half
- 00:00:15 sized arrays recursively and then sorts
- 00:00:19 those smaller arrays until it finally
- 00:00:21 builds the raise back up to build this
- 00:00:26 final sorted array so how does how do we
- 00:00:30 what is the runtime of this well let's
- 00:00:32 analyze it so I'm gonna race all this
- 00:00:34 stuff real quick so Mercer takes an
- 00:00:39 array of size n as I said and it splits
- 00:00:42 it into two and over two sized pieces
- 00:00:47 then sorts those recursively so it keeps
- 00:00:50 bringing it into smaller and smaller
- 00:00:52 half sizes
- 00:00:53 so we have T of N equals 2 T of n over 2
- 00:01:00 and then finally it takes on each step
- 00:01:04 it takes the two half sized arrays and
- 00:01:08 then continually compares the smallest
- 00:01:11 element in each array creating one
- 00:01:15 larger array but to do this it needs to
- 00:01:18 look at every element to make sure that
- 00:01:20 they're all you know sorted in the right
- 00:01:21 way
- 00:01:22 so this final step takes o of n so what
- 00:01:27 is the runtime well I think it's easiest
- 00:01:30 to solve recurrences by listing off what
- 00:01:32 the F of n is and what the N log base B
- 00:01:36 of A is so f of n in this case is
- 00:01:40 function o of n n log base B well this
- 00:01:45 is our B this is our a so n log base B
- 00:01:50 of A is n to the log 2 of 2 so 2 to the
- 00:01:56 what equals 2 well it's just 2 to the 1
- 00:01:59 so I can simplify this to be n to the
- 00:02:03 first so how it is even compared to end
- 00:02:08 the first
- 00:02:09 well it's Theta bounded by n to the
- 00:02:12 first
- 00:02:13 so when our F of n is Theta bounded by
- 00:02:16 this n log base B of A
- 00:02:18 well that is case two of the master
- 00:02:22 method so case two says to find our
- 00:02:25 asymptotic run time when we have an F of
- 00:02:29 n that is Theta bounded by n log base B
- 00:02:35 of A two I guess we could also mention
- 00:02:38 the factor of log to the K and in this
- 00:02:41 case K is just equal to zero so that
- 00:02:43 can't term doesn't really actually
- 00:02:44 affect this one but if this is the case
- 00:02:46 then our run time T of n is going to be
- 00:02:51 equal to theta of f of n so f of n is
- 00:02:56 just n so T of n is bounded by theta of
- 00:03:00 n and then we just have to do the log
- 00:03:02 with them remember the log K plus 1 term
- 00:03:05 so if we have analogue to the 0 n
- 00:03:07 originally now we have log to the first
- 00:03:10 power of n so we have n log n so using
- 00:03:16 case two of the master method we get
- 00:03:17 theta of n log n for the recurrence
- 00:03:22 runtime of merge sort