Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science Introduction to Data Structures The Merge Sort Algorithm Evaluating the Runtime of Merge Sort

Posted by J R
J R
Courses Plus Student 12,168 Points

Why does the implementation of split take O(kn log n). What is the difference between 'k' and 'n'?

Is it that 'n' is the number of elements in a list and 'k' is the number of splits being performed?

1 Answer

Blaise Gratton
Blaise Gratton
30,213 Points
Blaise Gratton
Blaise Gratton
30,213 Points

Not quite - n represents the number of operations to perform over the collection, while k represents the subset of n that is used for the slice operation. k could be anywhere from 0 to n, depending how much of the list we are copying during each slice operation. We use a different letter to represent this operation because we know it's smaller than n but still affects the overall runtime complexity.

The number of splits being performed is where the log n comes in, since we're halving the list each time.

Here's a breakdown:

Halve the list until we have individual elements (this takes log n time or O(log n)) -every time we're halving a list, we are using the list slice operation, which takes linear time -but we're not slicing and copying n each time, it's a subset of n we call k, but still linear time (so k time or O(k))

Once we've broken down n into individual lists (which took O(k log n)), compare each element as you zip it back up together (this takes n comparisons), leaving us with O(kn log n)

Hope this helps!