Yes. It is obvious that your algorithm uses $$$O(1)$$$ space (ignoring the compulsory extra vector that you have to create as a return value).

Your algorithm uses $$$O(n)$$$ time (if properly implemented). Since the sample space remains the same throughout, we can say that each trial is independent. Furthermore, each trial has a binary outcome (fail/success).

Let $$$X$$$ represent the number of trials needed to get all the majority elements. Obviously, we can have at most 2 such elements. So let's assume that we have the worst case (i.e. there are exactly 2 of them with the lowest frequency possible).

Let $$$p$$$ = probability of success (we find a new majority element) $$$\approx \frac{1}{3} $$$.

Then $$$X$$$ follows a negative binomial distribution.

Since $$$E(X)=\frac{r}{p}$$$, where $$$r$$$ is the number of successes required, we have $$$E(X)=\frac{2}{p}=6$$$

Since you have a linear scan of the array on each of the 6 iterations, your algorithm will take on average $$$O(6*n)=O(n)$$$ time. Therefore, your algorithm's time complexity is linear which was what we wanted to prove.

Edit: This proof works given that the solution limits the number of iterations.

Let's consider an array with no repeated numbers. In order to complete the outer loop we must mark off at least 2/3rds of them. Each mark must run through the inner loop once, taking n time. Therefore we must be at least 2/3 * n^2 time in the worst case, ignoring misses. If we factor in misses we have a 1/3 chance or better of finding some element so we can expect less than 3 * (2/3) * n average misses total.