I'm getting a little confused about these two different approaches to express the time complexity of an algorithm.
In general, What is the relation between these two notations?
Thanks
EDIT
Erased some wrong content that is also independent of the answer to my question.
The notion of time complexity is basically used to estimate how well a certain algorithm performs as you scale up the size of the input. For that, it is common to express the time required to complete the algorithm as a function of the size of the input, and to look at the asymptotic behaviour of that function. Because this is only to get an idea of the scaling behaviour, we don't really need to care about the specific constants and coefficients in that function, hence the use of the "big O" notation.
With that said, I've never heard about expressing time complexity as a "function of the size of $n$", because that doesn't really makes sense. It would be useful if you could provide a link or quote where you've seen that. Without that information, I would assume you just misunderstood what you read. This confusion could be due to the various methods people can use to estimate time complexity.
Make your life simpler...
From the formal definition of time complexity, the input size of an algorithm should be expressed in the number of bits required to represent the data in a computer memory. In practice, people rarely use that number of input bits directly, since it is annoying to do so. In addition, there are several simplifying assumptions that are usually true, and that allow you to use a different number as input size, and still reach the proper time complexity.
For instance, you mentioned the binary representation of a number in an input array. In many cases, the binary representation of an integer is considered to have constant size, say $k$ bits for one integer. Hence the input size in number of bits $N$ would be a factor away from the input size in number of integers $n$, $N=kn$. And because $k$ is constant, you have $O(N)=O(kn)=O(n)$. This also holds for other functions like logarithm, polynomials, etc. So for all intent and purpose, you can use the number of integers $n$ instead of the number of bits $N$.
Another problem with the bits size $N$, is that it varies based on the representation. Say you don't want to waste memory for integers that have a smaller binary representation than your largest integer. Then you concatenate every binary representation, and give that concatenation to your algorithm. Your array of integers is effectively just a bunch of bits. Then your algorithm needs some way to figure out where a given integer is in your bunch of bits, so you actually have to provide extra data to be able to interpret that bunch of bits. Now, how do you account for the extra time cost of figuring out what each integers are? This extra cost should be part of the final time complexity. With representations of equal size, figuring out where any integer is, is simple. When you have different sizes, you need to lookup the proper location first. Would that change the resulting time complexity? In this particular example, probably not. But another type of representation could have a non-negligible impact on time complexity.
In general, you can imagine many different types of representation for the same raw data. Each representation may take a different amount of space, and incur a different lookup cost, that may or may not have an impact on the final complexity. Thus it is much more handy to consider input size as the number of items you have to handle, rather than the underlying number of bits they take up in memory.
...but life isn't simple
Now of course, if the simplifying assumptions do not hold, you have somewhat of a problem with the estimated complexity. In some cases, you may need to handle integers whose binary representation are arbitrarily large, so performing arithmetic operations on these integers can also take an arbitrarily large time. Those issues are often disregarded completely. The complexity of an algorithm is in essence nothing more than a theoretical indication of how well the algorithm scales with input size. The actual time performance will depend on the implementation and the hardware. Some applications could also have skewed input, resulting in some algorithms with bad average/worst case performances to outperform another algorithm with better average/worst case performance.
With that much variability, it is the responsibility of the software engineer to choose the appropriate algorithm for a specific application, with the appropriate data structures. And to achieve that, it is the responsibility of computer scientists to appropriately document their algorithms, so other people can estimate how well it performs in certain circumstances. And to communicate what circumstances are desirable/undesirable for an algorithm, you should take into account worst/average/best case analysis, but also the underlying model of computation.
For instance, in computational geometry, people often use the real RAM model, which is pretty unrealistic, but still gives an appropriate idea of the complexity of an algorithm.
Miscellaneous mistakes
This as already mentioned in comments, but your post contains several confusing statements. The standard argument for the worst case analysis of quicksort yields an $O(n^2)$ complexity, and its average complexity is $O(n\log n)$.
Also, $n!$ is not equal to $O(n\log n)$. The only relationship between $n!$ and $n\log n$ I can think of right now is this: $$\log(n!)=\sum_{i=1}^n\log i=O(n\log n)$$ which implies that $n!$ grows a lot faster than $n\log n$ does (as $n$ goes to infinity).
On a side note, the only sorting algorithm I know that reaches a complexity of $O(n!)$ is the bogosort. Thankfully, there are much more efficient sorting algorithms.