Coding

# Solving Recurrences Example – Merge Sort (Master Method)

• 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