SOLVED!
First of all I should've built my ComplexOperations sources with the toolchain provided by the Android NDK, as the documentation clearly states not to cross-compile with gnu compilers. So that was my first mistake. That alone didn't yet solve my problem as I still got the complex.h not found error when I do an ndk-build. The Android NDK contains a VERY limited implementation of the Standard libc. To solve this I used CrystaX NDK, an extended implementation of Android NDK. That solved everything!!