Welcome to the Treehouse Community
Looking to learn something new?
What's the difference between Big O of n and Big O of k?
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 Parker216,083 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! 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 FreemanTreehouse Moderator 67,989 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
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
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
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.