Big O notation question for set insertion with sequential scan? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:28:14Z https://cs.stackexchange.com/feeds/question/63962 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/63962 0 Big O notation question for set insertion with sequential scan? Evan Carroll https://cs.stackexchange.com/users/8279 2016-09-27T16:38:56Z 2016-09-27T18:50:56Z <p>A friend and I are asking some questions on <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow">Big O Notation</a>.</p> <ol> <li>We have an operation that requires a sequential scan on insertion of an element O(n). </li> <li>The insertion itself of an element is O(1).</li> <li>We are inserting a whole set of <em>n</em> items.</li> </ol> <p>We both agree the time for insertion is <em>O(n+1)</em> or simply O(n) reduced. But, we have two questions..</p> <ol> <li>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?</li> <li>Can we ever say the time for an "insertion of a whole set of n size is O(n**2)" per the above?</li> </ol> https://cs.stackexchange.com/questions/63962/-/63965#63965 2 Answer by gardenhead for Big O notation question for set insertion with sequential scan? gardenhead https://cs.stackexchange.com/users/18181 2016-09-27T16:56:16Z 2016-09-27T16:56:16Z <p>First of all, let's get some things straight. Big-Oh notation is just a notation for describing the asymptotic behavior of <em>any</em> mathematical function (well, at least those defined on the real numbers). It is <em>not</em> tied to algorithm analysis.</p> <p>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 <em>worst-case</em> bound on the run-time of $p$.</p> <p>Now, it may very well be the case that</p> <p>$$T(p(x)) \leq e\times n^{3/2} + 2.73 \log_{\pi} \sqrt n \times + .23432342$$</p> <p>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</p> <p>$$T(p(x)) = O(n^{3/2})$$</p> <p>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.</p>