2

Forgive my ignorance here. I am referring to logarithm base 1 which is undefined (https://arbital.com/p/log_base_1/)

I am learning the time complexity in programming and logarithm in mathematics.

Logarithm base 2 of 32 is 5, and if I correlate that to the time complexity to find an element in a sorted array of 32 elements using binary search, it would at most take 5 steps to find the target element using binary search, which is O(log₂ n). Also, according to my understanding of logarithm, if I split the array into 3 parts to search the target element, it should be a ternary search instead of binary search and the logarithmic complexity would be of base 3 instead of base 2 which is O(log₃ n), and in all cases, n = 32 because that's the number of elements in the array here.

Now, in mathematics, the logarithm base 1 is undefined, but if apply the above analogy and do a search for a target element in the same sorted array mentioned above, but without splitting at all, it would equate to O(log₁ n) (this is my assumption here) which practically would be O(n) and linear. So shouldn't (log₁ n) = n?

I was referring to the Ternary search as explained here https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/#:~:text=Like%20linear%20search%20and%20binary,which%20part%20the%20element%20exists.

Thanks in advance.

nohup
  • 121
  • 6
    I disagree with your analogy. If $\log_2$ corresponds to splitting into $2$ pieces and $\log_3$ corresponds to splitting into $3$ pieces, then $\log_1$ should correspond to splitting into $1$ piece, i.e., not splitting at all. And that method of searching doesn't work. – Andreas Blass Jul 15 '23 at 23:34
  • Thank you @AndreasBlass. Could you kindly explain further why the analogy is wrong? The logarithmic complexity is explained in https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/#:~:text=Like%20linear%20search%20and%20binary,which%20part%20the%20element%20exists. under "Complexity" – nohup Jul 15 '23 at 23:58
  • So if you split an array of length $32$ into $32$ groups, then you can find the element in a single step? – aschepler Jul 15 '23 at 23:59
  • 1
    If you split the array in one piece (don't split it), that doesn't tell you anything, unless you count "if the element is in the array, it is in one of the array's 32 positions". That's not a search algorithm at all. – aschepler Jul 16 '23 at 00:01
  • Thank you @aschepler. Would you be kind enough to elaborate it as an answer? Also, how and is the time complexity described as O(log₂ n) and O(log₃ n) for binary and ternary search according to the link above? – nohup Jul 16 '23 at 00:06
  • @aschepler also, if my understanding here is flawed, could you kindly point out what is wrong with my understanding? Thanks again. – nohup Jul 16 '23 at 00:08
  • 1
    Your understanding is a little like saying that $n/.1$ is $O(n)$, and $n/.01$ is $O(n)$, and $n/.001$ is $O(n)$, and so on, so why isn't $n/0$ also $O(n)$? You are trying to take a limit, where taking a limit is illegitimate. – Gerry Myerson Jul 16 '23 at 01:06
  • 1
    Since $\log_3 n = (\log_3 2)\log_2 n$, and since big-O notation allows a function to be multiplied by any constant without changing its big-O class, $O(\log_3 n)=O(\log_2 n)$. So there isn’t even a “trend” for you to extrapolate backward from ternary and binary search toward linear search. All searches that split the array in some number of equal pieces have exactly the same general asymptotic complexity, $O(\log n)$, whereas the $O(n)$ search has a different complexity altogether. – David K Jul 16 '23 at 01:20
  • Thank you @DavidK . I didn't realise log3n=(log32)log2n although I was aware of eliminating constants. Would you be kind enough to write it as an answer and I will accept it. Does it also mean, for both binary and ternary search, the time complexity can be concluded as O(logn) ? – nohup Jul 16 '23 at 01:26
  • 2
    @GerryMyerson I get the idea of the limit now, thank you. – nohup Jul 16 '23 at 01:29

0 Answers0