¿Se puede encontrar la intersección de dos listas en menos de tiempo lineal (las listas están ordenadas)?

Manash ha explicado adecuadamente por qué no puede ser sub-lineal, pero creo que vale la pena mencionar una optimización simple:
Si espera tomar una intersección, puede agrupar los valores en la lista (use un hash si no son numéricos), y luego su intersección será lineal en el número de cubos en lugar de la longitud de las listas.
Esto se reduce al caso basado en la longitud si todos los elementos en cada lista son únicos, pero si existen duplicados, también puede guardar un factor log (n) al no tener que ordenar (suponiendo que los cubos no se conocen de antemano, lo que hace que la ordenación de conteo inaplicable), y el hecho de que la clasificación ya no es necesaria significa que puede intersectar elementos sin ningún orden definido. También te deja con valores de depósito de nuevo, por lo que te compones en las ganancias si estás intersectando un montón de listas.

Por ejemplo, considere la intersección de cinco listas, cada una con 100 enteros del 1 al 10.
Hacer una intersección en dos listas sin ordenar es O (n ^ 2), por lo que cada intersección toma más de 10,000 comparaciones, para un total de 40,000 comparaciones en el peor de los casos.
Si hacemos una clasificación O (n) en cada lista y luego hacemos cuatro intersecciones O (n), tiene un total de 900 comparaciones en el peor de los casos.
Pero si primero agrupamos todos los valores, podemos hacer intersecciones en O (#buckets): 5 * 100 (bucket) + 4 * 10 (intersect) = 540 comparaciones.

Sí, se puede encontrar si crea una estructura de datos diferente de las listas. La estructura de datos se explica a continuación, a partir de cada elemento de la lista A, construya un árbol binario con los elementos de la lista B, de manera similar, a partir de cada nodo de la lista B construya un árbol binario con los elementos de A, será una estructura muy compleja pero la complejidad debe estar en algún lugar, O (log (n) * log (n)).

No, informalmente, considere el caso de dos listas A y B de modo que A = B (en orden). Todavía hay que verificar cada elemento de A contra la posición correspondiente en B.
Sin ninguna otra restricción, parece ser siempre lineal.

El mejor caso puede ser menos que lineal, pero hoy en día a nadie le importa. Entonces no.