Coding

Solving Recurrences Example – Merge Sort (Master Method)

2 years ago
  • 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

You may also like