Comparación de la complejidad de O (n + m) y O (max (n, m))

Tuve una entrevista de trabajo hoy. Y se le preguntó sobre la complejidad destd:set_intersection. Cuando estaba respondiendo, mencioné que

O (n + m)

es igual a:

O (max (n, m))

Me dijeron que esto es incorrecto. Intenté sin éxito mostrar equivalencia con:

O (0.5 * (n + m)) ≤ O (max (n, m)) ≤ O (n + m)

Mi pregunta es: ¿soy realmente incorrecto?