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 trialokilydokily
12,105 PointsWhat's the difference between Big O of n and Big O of k?
.
3 Answers
Ikuyasu Usui
36 PointsBecause 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
231,184 PointsIt 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! And for some holiday-season fun and extra practice, give Advent of Code a try!
Tonight's puzzle (# 9) defintely required an awareness of algorithm complexity!
Chris Freeman
Treehouse Moderator 68,441 PointsSteven 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
231,184 PointsAre 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
Treehouse Moderator 68,441 PointsI think we are in agreement and saying the same thing.
Steven Parker
231,184 PointsOk, good. I guess I misinterpreted the term "partially correct"