Mazdak Farrokhzad edited f) Size of the input.tex  almost 10 years ago

Commit id: aa90be270a8e8caf4ec5e779c59904b9ca92f028

deletions | additions      

       

\newcommand{\card}[1]{\left\vert{#1}\right\vert}  Let $K$ be the set of courses for a particular problem instance $I$. The Since we are assigning a "constant cost to every machine operation" in UCC, it's a bit fuzzy how to view the input size when dealing with complex objects. Should we view each object as a whole, or as it's components?  If we view each $course \in K$ as a single object, the  size of our problem therefore becomes equal to the number of inputs, courses, that is the cardinality of $K$, so  in our case courses: $\card{K}$. case: $n = \card{K}$.  If we instead split up each course into it's components and view the totality as two arrays of start times and end times - we instead get $n = 2\card{K}$.  \subsection{Logarithmic cost criteria}  For each course, we have two attributes which contribute to the size of our input: a start time and a finish time. This means that in logathimic cost criteria, the problem size for the same problem $I$ would be: