0

Hi guys I am practicing my algorithm and complexity theory. I want to know what is the order of complexity of the algorithm developed taking the x-axis as the size of the vector? (Big O notation). This is the piece of code that I took and Algorithm to return all combinations of k elements from n and just modify a little bit

import java.util.Arrays;

public class BigOExample {
    public static void main(String[] args){
        Integer[] arr = {12,24,31,43,55,61};
        combinations2(arr, 4, 0, new Integer[4]);
    }

    static void combinations2(Integer[] arr, int len, int startPosition, Integer[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

Thank you very much!!

Nicolas
  • 1,193
  • 1
  • 10
  • 25
  • Please see the following in StackOverflow: https://stackoverflow.com/questions/24643367/whats-time-complexity-of-this-algorithm-for-finding-all-combinations#:~:text=The%20complexity%20is%20O(C,%2C%20n%5E(n%2Dk)))%20. – Mark Lavin Dec 07 '21 at 18:47
  • The good news is, your algorithm is not inefficient, so its complexity is proportional to the length of its output. But the output is actually quite long (because there are a lot of combinations, especially if n is large and k is close to n/2) – Stef Dec 07 '21 at 19:12
  • Thank you for your answers. Now after a look to @MarkLavin I would say this is more like n!/k!(n-k)! (with k = 4, in this case) what do you think ? – Nicolas Dec 07 '21 at 19:26
  • That makes sense. – Mark Lavin Dec 07 '21 at 19:29

0 Answers0