Big O notation question for set insertion with sequential scan? A friend and I are asking some questions on Big O Notation.


We have an operation that requires a sequential scan on insertion of an element O(n). 
The insertion itself of an element is O(1).
We are inserting a whole set of n items.


We both agree the time for insertion is O(n+1) or simply O(n) reduced. But, we have two questions..


Does Big O Notation ever refer to the time for a set operation such as insertion of a whole set, or only to an individual elements operation on the set?
Can we ever say the time for an "insertion of a whole set of n size is O(n**2)" per the above?
First of all, let's get some things straight. Big-Oh notation is just a notation for describing the asymptotic behavior of any mathematical function (well, at least those defined on the real numbers). It is not tied to algorithm analysis.

Performing algorithmic analysis on a program $p$ that takes input $x$, you want to find a function $f(n)$ so that, for every input $x$ of size $n$, one has $T(p(x)) \leq f(n)$, where $T(p(x))$ denotes the run-time of a program. That is, we are finding the worst-case bound on the run-time of $p$.

Now, it may very well be the case that

$$T(p(x)) \leq e\times n^{3/2} + 2.73 \log_{\pi} \sqrt n \times + .23432342 $$

However, this is not very useful. It's difficult to conceptualize the growth of this function. That is one reason we use asymptotic bounds (the other being it is often easier to determine the asymptotic behavior than the exact behavior). It is much more approachable to write

$$ T(p(x)) = O(n^{3/2}) $$

Anyway, to answer your question: you'll note here that $p$ is an arbitrary program. You can take that program to be whatever you like, including "insert $n$ elements into the set". No one can tell you what to analyze.