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 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
216,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! :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 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 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
216,083 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 67,989 Points

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

Steven Parker
Steven Parker
216,083 Points

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