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 Exploring Arrays Array Search, Insert and Delete

What's the difference between Big O of n and Big O of k?

.

3 Answers

Because n is already used to represent the number of elements in the original array in our context, k is used to represent the number of elements in the array appended to the original array. That's all. You could probably say Big L or BIg J if you specify it as the number of elements in the appending array.

Steven Parker
Steven Parker
231,184 Points

It would depend on what you mean by "k". If you're referring to the point in the video where he says "This operation has a run time of big O(k), where k represents the number of elements in the list that we're adding to our existing list." then it's essentially the same thing as O(n), or linear complexity. The difference is that the complexity is based on the size of the added list (k) instead of the size of the original list (n).

If you're intersted in common algorithm complexities, I found this Big-O Cheat Sheet you might like.

Happy coding! :christmas_tree: And for some holiday-season fun and extra practice, give Advent of Code a try! :santa:
Tonight's puzzle (# 9) defintely required an awareness of algorithm complexity!

Chris Freeman
MOD
Chris Freeman
Treehouse Moderator 68,441 Points

Steven is partially correct in that O(k) is linear runtime similar to O(n) but differs in that k is not dependent on the size of the list n.

On a list, inserting and deletion take O(n) linear time because regardless of where the change is made, every element may have to be adjusted to update that elements index value. So as the list grows, insertions and deletions take longer and longer [as was quickly discovered in today's Advent of Code challenge Day 9].

Also on a list, a series of appends or a pops take O(k) near-constant time because, independent from the size of the list, the appending or popping takes a constant time for each element added or removed. Since k does not grow in size as the list grows in size, it is more of a "konstant" time. Think of O(k) as k * O(1) time. Of course, if k were to track the number of items in the list. Then it wouldn't be a "k", it would be an "n" instead.

Steven Parker
Steven Parker
231,184 Points

Are you sure "that it is not dependent on the size of the list"? I figured that it was, since what the instructor says right before the part about O(k) is "Extend effectively makes a series of append calls on each of the elements in the new list".

That's why I said first that it depends on what you mean by "k", because if it was not related to the size of the list I would have said it was the same as O(1). And it's O(k) instead of O(n), because while it is dependent on the size of the new list (k), it is not on the size of the old list (n).

Chris Freeman
Chris Freeman
Treehouse Moderator 68,441 Points

I think we are in agreement and saying the same thing.

Steven Parker
Steven Parker
231,184 Points

Ok, good. :+1: I guess I misinterpreted the term "partially correct" :wink: