I really recommend trying to learn just the basics about big-O, because it is really the single most important thing that a CS degree teaches you.
Yeah, I agree.
You can learn it in like 30 minutes, and understanding the concept behind it (not just the notation) is the core of understanding why some algorithms work better than others.
Industry specific certifications can help ease the way into the job market along with a portfolio of (side) projects.