Artificial Intelligence - Why I (compSci undergrad) think the concept of an AI being unimaginably faster than humans is a flawed argument. Am I missing something?

It seems like there is a common belief that AI will inherently be unimaginably faster than humans. For example Sam Harris talks about how an AI could do the work that would take a human thousands of years in a single day. This same concept is expressed beautifully in the fictional film her. If you haven't seen the film you might want to avoid watching the linked clip.

What I've learned about computation theory (ungrad CompSci graduate) leads me to believe that while it's entirely possible for an AI to be faster than a human I don't believe it will be as significant as the above two examples make us believe. To me they are arguing that humans are O(1,000,000,000n) and an AI is O(n).

When we compare algorithms using BigO we don't care about coefficients. As soon as we start looking at larger problems with larger data sets those big scalers quickly become insignificant. If we have a problem that takes 1,000 years to compute does it really matter if the human requires a week to write the program but an AI can do it in half a millisecond? The difference between 365,000.000000000005 days and 365,007 doesn't really matter does it... Even if the computation was a only a year the extra week is't that significant.

This example isn't that crazy yet the common belief is that an AI would arrive at the exact answer faster than we ever could. I just don't see what little I know about computational complexity that being able to scale up by any factor will matter. You have a an obvious bottleneck.

Am I missing something or is AI going to lack absolute certainly and be prone to making mistakes just like us because the computational cost for getting the best/exact solution is just too computationally expensive. Even if we learn something radically different like P = NP aren't there still enough unsolvable problems forcing you to always rely on an educated guess?

Thoughts?

EDIT: Statements like this I don't think we really know the algorithms of the biological brain yet. However, I think it's a common belief we don't run off logic gates. There is no clock cycle. It's a completely different architecture. I don't think our minds look for exact solutions to problems instead look for solutions that fit patterns. 1+1=Turtle can be true statement in our minds but not true for a traditional computer. The fact that a computer can compute simple arithmetic faster and more accurately than an human seems to imply that all computation is faster which doesn't sit right with me. Not because I don't believe it can be possible but I don't believe I've seen evidence of this.