Quindi effettivamente è ottimo se f(n)=O(g(n))
Ni, f(n) è una funzione nella dimensione dell'input, ovvero n, ma la dimensione dell'input non ci dice niente a proposito della complessità dell'algoritmo.
Ad esempio considerando l'insertion sort su un array di dimensione n ha complessità n se l'array è già ordinato (caso migliore), invece n^2 se non lo è (caso peggiore).

Quindi un algoritmo è ottimo se la sua funzione di complessità nel caso peggiore è O-grande della funzione che rappresenta il limite inferiore del problema.

ovvero se f(n) <= c * g(n) dove c è una costante positiva?
Esatto, ma la relazione vale solo definitivamente, ovvero esiste un N tale che per ogni n maggiore di N, f(n) <= c * g(n), dove c è una costante reale positiva.
La costante moltiplicativa c serve solo a dire che siamo interessati esclusivamente all'andamento asintotico di f e di g e che se ad esempio g = 2x e f = x possiamo ancora considerare f <= g