Non credo di aver capito bene, però ci provo.

Possiedi una lista di nodi, dove ogni elemento è a sua volta una lista, creando così una sorta di "matrice"?

Inoltre non mi è chiaro questo:
eseguendo una ricerca completa per tutta la lista più (nel caso peggiore)eseguendo una ricerca solo sulla lista pricipale
Puoi definire la differenza tra "tutta la lista" e "solo la lista principale".

Per me il caso peggiore è la ricerca su tutta la struttura e non solo sulla lista principale.

E questo è il dubbio.

Tornando a quello che chiedi:
il tempo era "teta(n)" ??!!??
Dipende molto da come interpreti n e da cosa rappresenta la lista.
N è il numero di informazioni che costituiscono il tuo problema (grandezza del problema), quindi è meglio se spieghi cosa vuoi realizzare e magari posti anche l'algoritmo in PseudoCodice in modo da chiarire anche che tipo di ricerca fai (binaria - lineare; iterativa - ricorsiva)