I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my calculations and analysis
The algorithm is very simple, don't worry. I won't write the code here but I will describe the algorithm and my analysis, perhaps someone will be able to help.
The question I was asked to solve is this:
Given 2 sorted arrays $A$ and $B$ such that $|A|=|B|$ and no element appears twice (Meaning no element in $A$ appears in $B$, no element in $B$ appears in $A$, and there are no recurring elements in $A$ or $B$), describe an algorithm that finds the median of the union of the two arrays in $O(\log n)$ where $|A|=|B|=n$.
What I did
I won't write down the small details of the algorithm or the computer code, but generally the algorithm works like this:
Step 1: Find the median of $A$ $m_A$ and the median of $B$, $m_B$. This can be done in $O(1)$ since they are sorted.
Step 2: if $m_A > m_B$ then discard all the elements of $A$ that are larger than $m_A$ and discard all the elements of $B$ that are lower than $m_B$. Otherwise, discard all the elements of $A$ that are smaller than $m_A$ and discard all the elements of $B$ that are larger than $m_B$. Note that from the definition of median this means we throw away half of the elements each time.
Step 3: if $|A|+|B| >4 $ then repeat step 1. else, just find the median of the $|A|+|B|$ elements in $O(1)$ since there are at most $4$.
The algorithm works. Here is an example:
Suppose $A=[1,12,15,26,38]$ and $B=[2,13,17,30,45]$.
Step1: Find the medians. $m_A=15$ and $m_B=17$.
Step2: discard the excess elements. Now $A=[15,26,38]$ and $B=[2,13,17]$.
Step1: Find the medians. $m_A =26$ and $m_B=13$.
Step 2: discard excess elements. Now $A=[15,26]$ and $B=[13,17]$
Step 3: we have total of $4$ elements, find the median in $O(1)$ time to get the correct result which is $17$.
What is the runtime of this algorithm? Well since we always throw away half of the elements (this is true from the definition of a median), I believe the recursion formula we have is something like $T(n)=T(\frac{n}{2})+O(1) = T(\frac{n}{4})+2O(1)=...=T(4)+\log nO(1)=O(\log n)$
Is this analysis correct?
Edit: To get a better idea of why this algorithm works (if you are interested in such things), realize that if for example $m_A > m_B$, then the median of the union is either an element of $B$ that is larger than $m_B$ or an element of $A$ that is smaller than $m_A$. So we narrowed our search region by a half. continue like this again until arrays are sufficiently small. same idea as binary search.