C/C++ - complessità computazionale

ciao ho svolto un programmino che genera un vettore di numeri casuali(con ripetizioni), poi una volta inserito un valore x cerca tutte le possibili coppie di valori presenti nel vettore che diano come somma x.
Se ho fatto bene i miei conti la complessità dovrebbe essere di circa O(n^2), è possibile ottimizzare il programma?

Ho provato a ottimizzare l'algoritmo in questo modo e spero che il ragionamento sia corretto:
1) ordino il vettore con merge sort) ->o(nlogn)
2) cerco le posizione dell'elemento x nel vettore (chiamiamo j la posizione) con la ricerca dicotomica-> o(logn)
3) cerco le posizione dell'elemento x/2(se esiste altrim in numero strettam minore)(posizione k) -> o(log(n/2))
3) effettuo i confronti sommando gli elementi con posizione da 1a k e gli elementi da k+1 a j -> caso peggiore: n^2/4, caso migliore: o(1)

di fatto non ho ottimizzato nulla!!! qualcuno sa aiutarmi???

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 1000
int main()
{
    long long int v[N]={0};
    int i=0;        //variabile decisionale per il riempimento
    int n=0;        //dimensione vettore
    int x=0;        // valore da cercare
    int yes=0;      //flag per sapere se è stato trovata almeno una coppia
 
    /************************************************************************
    *           RIEMPIMENTO VETTORE                 *
    ************************************************************************/
    printf("Inserisci dimensione del vettore\n");
    scanf("%d",&n);
    printf("digita:\t1 per inserimento da input\t2 per inserimento automatico casuale\n");
    scanf("%d",&i);
 
    srand(time(NULL));
 
    if (i==1)   for (int j=0; j<n; j++)  scanf("%d",&v[j]);  //inserimento manuale
    else        for (int j=0; j<n; j++)   v[j]=rand();       //inserimento automatico
 
    for( int j=0; j<n; j++)   printf("v[%d] = %d\n",j+1,v[j]);   //stampa vettore
 
    /************************************************************************
    *               RICERCA                 *
    ************************************************************************/
    printf("\ninserisci un valore compreso tra 0 e %d\n",RAND_MAX);
    scanf("%d",&x);
 
    for(int j=0; j<n; j++)
        for(int k=j+1; k<n; k++)
            if(v[j]+v[k]==x) {printf("\nv[%d]+ v[%d] = %d + %d = %d \n",j+1,k+1,v[j],v[k],x); yes=1;}
 
    if(yes==0) printf("\n non ci sono valori nel vettore la cui somma sia uguale e %d\n",x);
 
    return 0;
}

Questo è un caso particolarissimo del problema del sottoinsieme somma (che è np-completo), dove la somma che vuoi ottenere è x e il sottoinsieme ha sempre cardinalità 2.

Dal momento che devi comunque sempre trovare una combinazione di due elementi, non potrai fare a meno di avere complessità n^2. Potrai al massimo diminuire il numero di iterazioni del caso pessimo di un fattore costante, ma n^2 rimane.

Se parti col merge sort potresti testare solo i primi k elementi minori di x/2 con i successivi h elementi maggiori di x/2 e minori di x. In questo modo scarti alcune combinazioni inutili. Infatti con il tuo algoritmo nel caso pessimo fai un numero di passi pari alla sommatoria di 1, 2, 3, ..., k+h-1, ossia (k+h-1)*(k+h-2)/2, quindi (k^2+2hk-3k+h^2-3h+2)/2; con questo ne fai solo kh. In breve questo approccio è più veloce per ogni h o k tali che la loro somma sia circa maggiore di 6, ossia per tutti i casi sensati per un'elaborazione.

Se il vettore o Array da testare verrà caricato con un numero abbastanza
elevato di elementi numerici, con un ordinamento del vettore tramite
QuickSort o MergeSort, potresti andare ad eslcudere gli elementi nel
vettore che sono uguali e maggiori del valore x, in modo da ridurre
il numero di iterazioni e confronti/somme da effettuare, in seconda fase
inizierai l'iterazione dal primo valore utile nel vettore verso il valore minimo
in modo tale che quando la somma tra i due elementi risulterà inferiore
al valore x, salterai i restanti valori da iterare, insomma più o meno,
lo scopo è quello di ridurre il numero di iterazioni e di somme.