aman_naughty's blog

Estimate time complexity of randomized algorithm
By aman_naughty, history, 6 years ago, In English

Problem : problem

Code :

code

. I want to know the time complexity of my algorithm. Although it runs within 16 ms on leetcode but is it really O(n) time and O(1) space??

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
← Rev. 7   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What happens in the case that we don't have any majority elements?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply