This is effectively doing a binary search, because it's dividing the problem space into two every time. The algorithm of binary search is, in the average case,
O(log n). Generally, with Big O, we want to use the average case if not otherwise specified. As a result,
O(log n) is the complexity of this piece of code as well.
For this one I thought at first "oh that's just O(n)" but intuitively I felt like this was incorrect. So I traced a quick test case, 16, in my head. I got up to 4 and exited the loop, then realized that due to the squaring of the numbers, the complexity of the algorithm was clearly
O(sqrt(n)), which the answer key confirmed.
This is
O(n) by definition of an unbalanced BST. If the search tree was balanced, the worst case would still be O(log n). But an unbalanced BST can just be a straight line of n nodes all the way down, which would require O(n) to find the bottom element -- hence, worst-case.
Ngl, I forgot the difference between a standard binary tree and a BST. So I had to look it up. A BST is ordered according to special criteria as follows:
The last bullet point confused me when I was in Data Structures, for some reason. It's just a fancy way of saying that the properties follow
all the way down the tree.
It follows that due to the lack of sorting, we could search up to n nodes to find the requisite value. So the algorithm is
O(n).
My initial instincts say "well, we're copying an entire array for every single value in the array, so we do n operations for every n, so that's O(n^2)" and I already forgot what the algorithm is even supposed to be doing. Lol. Oh, right, we're appending a value to the array in an extremely inefficient manner. If we check the answer key we see that I am correct. This algorithm is in fact
O(n^2).
Well, my daily algorithms hour is up, so back to work ig.
Comments
Post a Comment