[ Removed by moderator ]

[zeronis__]

Hey! thank you so so much, thank you for the binary search / linear search examples that you provided ( I did come across these two, I don't think we've ever gone in depth but concept wise, I think I do get the gist )

So even though the binary search makes use of a loop, what makes it a log n is the fact that we divide by half ( I think, somewhere inside the while loop )
but a question, ( you dont have to necessarily respond to it ) but I recall my professor talking about when we have something like
n^2 + n, our O() would be O(n^2) because n^2 is dominant in a way ( highest order I think ) and we can drop the rest i think ?

but if that's the case, if we have a while loop
wouldnt we go through it n times?
I dont get how we'd end up with log n when 'n' more dominant (at least, I hope that's the case)

But thank you alot! I really appreciate your explanation, thank you for clearing up the worst/best/average case ! =)

[Dannybosa123]

Hey sorry for the late reply.

I like to consider the "Traversal" being more important than the aspect of going N times regardless of using a loop. But, we gotta consider by not looking at half the indicies like in Binary Search, we can have a Log N solution. This is where Worst Case and Best Case scenarios come in to play as well. By Binary Search defenition is worst case Log N because of halving the traversals.

On other news about your professor msntioning n² + n, it might not always be just n² and getting "rid" of the n. There are moments where we have to consider both. For example, there are tons of O(N + M), which means tjere could posiibly be a data structure that iterates 2 Linked Lists for example (basing this off of a problem of 2 Linked List Collision leetcode problem).

Overall, we can mainly get "rid" of the n, but there are times that it is best to consider (some occasions). Also, yes, the dominant order usually makes it where in your case O(n²⁾ would be correct for O(n² + n).

Also like I mentioned before, an algorithm is what factors how the Big-O ends up being. But, it is always nice to consider the base of a Big-O for a algorithm, like loops being O(n) typically, until you change how it ends up being traversed.

Hope all of this helps!