1

I have written the following Java code for calculating the number of 1:s found in a bit vector using a Divide and Conquer method. I'm trying to figure out the time complexity of the algorithm "count" assuming we have a function IsZero(int []arr, int low, int high) that (perhaps unrealistically) runs in O(1) which returns true if all the bits between low and high are 0. I will include a main method which explains how the algorithm can be used, and also my own implementation of IsZero (which doesn't run in O(1) complexity). So, the question is. What is the time complexity of this algorithm given that IsZero has O(1) complexity?

Class Algorithm {

   static int NumberOfOnes(int v[]) {
       return count(v, 0, v.length-1);
   }

   static boolean IsZero(int arr[], int low, int high){
     for(int i = low; i <= high; i++){
         if(arr[i] == 1){
            return false;
         }
     }
     return true;
   }

   static int count(int arr[], int low, int high){

         if (low == high && arr[low] == 1) {
             return 1;
         }
         
         if (high - low == 1) {
             return arr[low] + arr[high];
         }

         if(IsZero(arr, low, high)) {
             return 0;
         }

         int mid = (low + high) / 2;
         return count(arr, low, mid) + count(arr, mid + 1, high);
   }

   public static void main(String args[]) {
       int arr[] = {1,1,0,0,0,0,1,0,1,1};
       int k = NumberOfOnes(arr);
       System.out.println(k); //Should print 5 as result
   }

}
  • How could `IsZero(...)` be O(1)? – Andy Turner Sep 24 '20 at 13:54
  • @AndyTurner It's part of the task to find out what the total complexity would be if it was possible for IsZero to be O(1), but I can't seem to figure out the complexity even though I have developed a working algorithm that solves the problem. If someone has a different solution to the same problem and they know the complexity of their solution, I would be glad to take a look as well. –  Sep 24 '20 at 14:06
  • Big O is the worst case complexity, so in case of isZero being O(1) you always assume it never passes and you have to do more work -> the whole problem reduces to divide and conquer visit all, O(n.log(n)). In case isZero is not O(1) but O(f(n)), you just multiply the whole thing with it and reduce = O(n.log(n).f(n)). – Vojtěch Kaiser Sep 24 '20 at 14:27
  • Look at your count method - in the worst case (all 1's) it's dividing the search space by 2 every time until you reach low=high (a single digit). You should recognise this as the same process a binary tree search requires, and therefore you can work out the complexity: https://stackoverflow.com/a/13093274/223806 – Paolo Sep 24 '20 at 14:42
  • @VojtěchKaiser it's not O(n log n), you're only searching one list. – Paolo Sep 24 '20 at 14:47
  • @AlgoGuy In your previous post you mentioned that you were interested in the complexity as a function of both the length `n` and the amount of ones `k`, perhaps you want to edit that into your post. – ADdV Sep 24 '20 at 17:40
  • @Paolo It is not search complexity as you visit all "list" nodes. It should do same amount of work as sort of an array. – Vojtěch Kaiser Sep 24 '20 at 18:17
  • @ADdV If that is the case then the complexity should be O(k.log(n)) as you effectively do k binary searches of O(log(n))? – Vojtěch Kaiser Sep 24 '20 at 18:22
  • I would like to know if the complexity is lower than or equal to O(1 + k*log(n)) where k is the number of ones. If this algorithm is too slow, does anybody have an idea as how I could solve it faster? –  Sep 24 '20 at 18:54
  • @AlgoGuy I'm pretty sure that is indeed the complexity. I'll write down an answer with an attempted explanation. – ADdV Sep 24 '20 at 22:01

1 Answers1

0

The complexity is O(1+k*log(n))

As is common with divide and conquer algorithms, you solve a larger problem by splitting it in two and solving both parts separately. This gives you log(n) "layers", where each subsequent has twice as many subproblems as the previous layer. However, we can discard some layers outright (if they have no ones), which means that at any point we're dealing with at most k subproblems. For each subproblem we call IsZero once, so we do at maximum k "things" a total of log(n) times, which leads to O(1+k*log(n)). Note that the 1 is added in case k=0.

But an even stricter bound is O(1 + min(n, k*log(n)))

Unlike other common D&C algorithms (say, MergeSort), you don't actually have a linear step at each layer. That means that in the worst case (where no subproblems can be discarded), you do at most 1 "thing" in the first layer, 2 "things" in the second, then 4, 8, 16 and so on until you do n "things" in the final layer. This sum equals 2n-1 which is of course O(n).

Therefore O(n) and O(1+k*log(n)) are both correct, and thus a stricter bound is O(1 + min(n, k*log(n))).

It's not terribly surprising that you can do this in O(n) of course, as the trivial solution is in O(n), but I found it to be a rather neat property of your algorithm.

ADdV
  • 1,162
  • 2
  • 16
  • @VojtěchKaiser The algorithm as described is in O(1 + min(n, k*log(n))). It need not have prior knowledge of k to achieve this. The min(f1, f2) is not because the algorithm can make some decision based on the value of k, but rather because both f1 and f2 are asymptotic upper bounds. – ADdV Sep 25 '20 at 00:25