Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

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

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,212 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!