Whats the time complexity of this function?

ghz 8months ago ⋅ 79 views

I made this function to remove all duplicate elements from a linked list and I thought the complexity was O(n^2) although tabnine says that the inner for loop runs k times where k is the # of unique elements in the linked list, therefore k is a constant and the inner for loop only has a complexity O(1). Im not sure which one is correct, could someone explain it to me?

void remove_dupes(struct node * head){
    if(head == NULL || head->next == NULL){return;
    }

    int *nums = malloc(1*sizeof(int));
    int k = 1; int max = 1;
    nums[0] = head->value; struct node *prev = head;
    head = head->next;

    while(head){ 
        int flag = 1;
        for (int i = 0; i<k;i++){ //runs k times where k is the # of unique elemnts in the list
            if (nums[i] == head->value){
                flag = 0;
            }
        }

        if(flag){
            k +=1;
            if(k>max){
                max = max*2;
                nums = realloc(nums,sizeof(int)*max);
            }
            nums[k-1]= head->value; prev = head; head = head->next;
        }
        else{
            prev->next = head->next; free(head); head= prev->next;
        }
    }
}

Answers

The time complexity of your remove_dupes function is indeed O(n^2), not O(k) as suggested by Tabnine. Let's break it down:

  1. Memory Allocation: The malloc and realloc calls have a time complexity of O(1) for each element they allocate, but they are executed potentially O(n) times, where n is the number of elements in the linked list. This is because each time you need to add a new unique element to the nums array, you may need to reallocate memory to accommodate the larger array.

  2. Nested Loop: The nested loop iterates over the elements in the linked list and the unique elements stored in the nums array. In the worst-case scenario, where there are no duplicate elements, the inner loop will run k times for each element in the linked list, where k is the number of unique elements encountered so far. Therefore, the overall complexity of this loop is O(n * k).

  3. Shifting Elements: When removing duplicate elements, you shift the elements in the linked list, which takes O(n) time in the worst case.

Combining these factors, the overall time complexity of your remove_dupes function is O(n^2), not O(k). While the inner loop does have a complexity of O(k) in some sense, it is nested within another loop that runs O(n) times, leading to the overall quadratic complexity.

#c