How can I determine the complexity of this small program?

Question

package maguen_3;
import java.util.Arrays;

public class Maguen_3_test {

    public static void main(String[] args) {
        randomPLaylist(10);

    }
    public static void randomPLaylist(int num) {
        int[] songsArray = new int[num];
        for(int i = 0; i < num; i++) {
            songsArray[i] = (int)(Math.random()*num) + 1;
            for(int j = 0; j < i; j++) {
                if(songsArray[i] == songsArray[j]){
                    i--;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(songsArray));
    }

}

This is a small program that shuffles a playlist. The function randomPlaylist receives the length of the playlist. I know intuitively that it is O(n * log n), but I don't know how to explain it with words.

Welcome to SO. Please clarify your question: what behaviour do you expect, what error do you get, etc. — Dmitriy Popov, Jul 11 '21 at 12:49

score 3 · Answer 1 · answered Jul 11 '21 at 11:59

It's not O(n*log n).

You should count the number of iterations of both loops.

The outer loop has num iterations. Let's denote num with n.

The inner loop has i iterations in the worst case (if the condition is never true).

The first time the inner loop runs it has 0 iterations.

The second time it runs, it has 1 iteration.

The last time it runs, it has n - 1 iterations.

Therefore the total time is 1 + 2 + ... + n - 1 = n * (n - 1) / 2 = O(n^2)

How can I determine the complexity of this small program?

1 Answers1