Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Data Structures!
You have completed Introduction to Data Structures!
Preview
Let's evaluate what the runtime and space complexity of our algorithm is now that we've implemented it.
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
How does memory usage grow
as the algorithm runs?
0:00
To answer those questions,
0:03
let's look at the individual steps,
starting with the split function.
0:04
In the split function, all we're doing
is finding the midpoint of the list, and
0:08
splitting the list at the midpoint.
0:12
This seems like a constant time operation.
0:14
But remember that the split
function isn't called once.
0:16
It's called as many times as we needed to,
0:20
to go from the initial list
down to a single element list.
0:22
Now, this is a pattern we've
seen a couple of times now, and
0:26
we know that overall,
this runs in logarithmic time.
0:29
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up