These fields are all optional and need only
be supplied if you would like a direct reply.
Subject
Your email address
Your real name
You must answer this!
If you don't, my spam filtering will
ensure that I never see your email.
What's 8 plus five (in digits only)?
Please make your changes here and then
Editing tips and layout rules.
File: AlgorithmsAndSizesOfInstances ''' <link rel="alternate" type="application/rss+xml" ''' href="/rss.xml" title="RSS Feed"> ********> width="25%" |>> ''' <a title="Subscribe to my feed" ''' rel="alternate" ''' href="https://www.solipsys.co.uk/rss.xml"> ''' <img style="border-width: 0px;" ''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png" ''' align="middle" ''' alt="" />Subscribe!</a> _ ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> <<| ---- My latest posts can be found here: * ColinsBlog ---- Previous blog posts: * IntroducingTimeComplexity * TheLinearFrog * SeventyVersusOneHundredRevisited * HowTheFarragoWorks * SeventyVersusOneHundred * PowersOfTwoInLexOrder * EmergingEExpanded * RageInducingSystemImplementation * TheBookIsNotAlwaysRight * EmergingE * ImpossibleToTranslate * WaitingInVain * NonRepeatingDecimals * RationalRepeats * WhyIsItLovely * CompilingCryptoConnections * ExploringConnectionsBetweenCryptoSystems * ElwynBerlekampHasLeftUs * RootCauseAnalysisAndThePhotocopierQuestion * TheUpDownTides * TheForeAftTide * TheSidewaysTide * WrappingUpWrappingUpTheEarth * TheOtherWrappingTheEarthProblem * WrappingTheEarth * TheRingOfSteel * RoundingUpTheRopes * OtherOtherOtherRopeAroundTheEarth * RopeAroundTheEarthRefined * TheOtherRopeAroundTheEarth * ElementaryEstimates * LatitudeCorrection * JustGiveMeTheAnswer * MoreMusingOnPollardRho * IdleThoughtsAboutPollardRho * WhenOptimisingCodeMeasure * ADogCalledMixture * AnotherPayPalScam * WhyTopPostingHasWon * UnexpectedInteractionOfFeatures * ArchimedesHatBoxTheorem * ConsideringASphere * ToLinkOrNotToLink * GenericAdviceForWritingAThesis * JustTeachMyChildTheMaths * NotASpectatorSport * LeftTruncatablePrime * TheDoctorAndTheLawyer * FourPointsTwoDistancesProof * MeetingRonGraham * NapkinRingVersusSphericalCap * TheFourPointsPuzzle * RadiusOfTheEarthPartTwo * GrepTimingAnomaly * TheRadiusOfTheEarth * ThisWorksToCureMyHiccoughs * PerhapsWeSavedOne * ThinkingAboutMastodon * DisappearingTrainsOnVirgin * TheIndependenceGame * OneOfMyFavouritePuzzles * ThinkingAboutRecursion * MemorisingTheTube * SpikeySpheres * SurprisinglyQuick * AnUnexpectedFraction * YouHaveToAdmireTheirOptimism * RepresentativesMatter * PythagorasByIncircle * APuzzleAboutPuzzles * HowNotToDoTwitter * Calculating52FactorialByHand * SmallThingsMightNotBeSoSmall * NotIfYouHurry * FactoringViaGraphThreeColouring * AnotherProofOfTheDoodleTheorem * WhenObviousIsNotObvious * GraphThreeColouring * TheDoodleTheorem * BeCarefulWhatYouSay * TheMutilatedChessboardRevisited * AMirrorCopied * TheOtherOtherRopeAroundTheEarth * PhotocopyAMirror * ThePointOfTheBanachTarskiTheorem * SieveOfEratosthenesInPython * FastPerrinTest * RussianPeasantMultiplication * FindingPerrinPseudoPrimes_Part2 * FindingPerrinPseudoPrimes_Part1 * TheUnwiseUpdate * MilesPerGallon * TrackingAnItemOnHackerNews * HackerNewsUserAges * PokingTheDustyCorners * ThereIsNoTimeForThis * PublicallySharingLinks * LearningTimesTables * GracefulDegradation * DiagrammingMathsTopics * OnTheRack * SquareRootByLongDivision * BeyondTheBoundary * FillInTheGaps * SoftwareChecklist * NASASpaceCrews * TheBirthdayParadox * TheTrapeziumConundrum * RevisitingTheAnt * TheAntAndTheRubberBand * IrrationalsExist * MultipleChoiceProbabilityPuzzle * RandomEratosthenes * WrappingUpSquareDissection * DissectingASquarePart2 * DissectingACircle * DissectingASquare * AnOddityInTennis * DecisionTreeForTennis * DecisionTreesInGames * AMatterOfConvention * DoYouNourishOrTarnish * BinarySearchReconsidered * TwoEqualsFour * TheLostPropertyOffice * TheForgivingUserInterface * SettingUpRSS * WithdrawingFromHackerNews ---- Additionally, some earlier writings: * RandomWritings. * ColinsBlog2010 * ColinsBlog2009 * ColinsBlog2008 * ColinsBlog2007 * ColinsBlogBefore2007 ******** [[[>50 I'm deliberately moving slowly and carefully here, trying not to do too much all at once. While the ideas here all seem to be quite straight-forward, we'll hit some tricky concepts quite soon. ]]] In the last post, IntroducingTimeComplexity, we look at what we mean by a "Problem", and by an "Instance" of a problem. To recap: * A *"Problem"* is a set of instances. * An *"Instance"* is a Challenge/Response pair. If it were simply a case of memorising all the answers then there would, perhaps, not be much of interest going on here. But it's not like that (and you probably never thought it was). No, for each challenge, we need a way of working out what the response should be. Such a method is called an *"Algorithm"* for that problem. So for the problem *MUL,* an /instance/ is a pair of numbers, and the desired response is the product of those two numbers. So *"23,*31"* is an instance of *MUL,* and the response on the other side of the card would be *713.* We need a way to compute that. So let's think carefully about algorithms. !! Setting the scene with addition We'll start with some school arithmetic. We learn how to add two numbers that each have a single digit. What is 3 plus 5? What is 4 plus 9? We learn these single digit sums, and if we forget the answer we can just count up on our fingers and toes. [[[>40 In case you're wondering, a *numeral* is a symbol or name that stands for a number. The number is an idea, the numeral is how we write it. ]]] But when we're given bigger numbers to add together, we run out of fingers and toes, and we are forced to use marks on paper. We can use tally marks, but when you have 1643 sheep it's a bit tedious to have to put a mark for each one. It's better to have the numerals, and then we want to be able to do arithmetic. So we learn long addition. (No, I'm not going to talk about long division!) We learn the process of writing out the two numbers, one above the other, and we add them in columns a digit at a time. If the total in a column is more than 9 then a "carry" spills over to the next column, and so on. It's pretty clear that bigger numbers take longer to add, simply because there is more to do. Twice the number of digits, twice the time taken. You might wonder if there would be a faster way to do this, a question we will return to time and time again, but since we have to look at every digit it seems reasonable that, broadly speaking, we can't do better. We could ask about using binary instead of decimal, or base 8, or base 60 (as the Babylonians did), and in fact if you've remembered all of your base 60 single digit sums, then because the numbers are shorter in base 60 it will take less time. But it's still the case that twice the digits will take twice the time. [[[>50 Detail: The exact time taken depends on the number of carries. To take that into account we always talk about /worst/case/ timings, and the timings are considered to be "upper bounds." A brief note about notation - I will sometimes use a "centre dot" to represent multiplication, as I have done here, sometimes use a "lower dot," sometimes use a "times" sign, and sometimes not have any symbol at all, using juxtaposition. It should, in each case, be unambiguous that I'm performing a multiplication, and my choice will largely be driven by aesthetics, although occasionally the need for clarity and explicitness will override that. However, if you feel strongly enough about this I invite you to email me to discuss it. ]]] Similarly, if we do it in binary each individual column might be quicker, but on average writing a number in binary takes 3 and a bit times as many digits as it does in base 10, so there will be three and a bit times as many columns to add up. But it's still the case that twice the digits will take twice the time. So the time taken to perform the addition is some constant times the number of digits. The exact constant will be different for different bases, /etc,/ but it will still be: |>> $T=c{\cdot}S$ <<| where $T$ is the time taken, and $S$ is the size (number of digits) of the numbers involved. We say that the time taken is a *linear* function of the size of the input numbers, where the "size" of the input numbers is not their value, it's the number of digits needed to write them down. So, to summarise: * A Problem is a collection of Instances; * An Instance is a Challenge/Response pair; * An *Algorithm* for a Problem is a process which, when given a Challenge, will compute the correct Response; * The *Size* of an instance is how many symbols are required to write down the Challenge. ---- |>> | |>> <<<< Prev <<<< ---- IntroducingTimeComplexity <<| | : | |>> >>>> Next >>>> ---- ConstantDifferences ... <<| | ---- ********> ''' <a href="https://mathstodon.xyz/@ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/images/Mastodon_Mascot.png" ''' width="256" height="280" ''' alt="https://mathstodon.xyz/@ColinTheMathmo" ''' /></a> ******** ''' <a href="https://mathstodon.xyz/@ColinTheMathmo/">You can follow me on Mathstodon.</a> _ _ _ _ [[[> ''' <a href="https://twitter.com/ColinTheMathmo">Of course, you can also<br>follow me on twitter:</a> ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> ''' <img src="/cgi-bin/CountHits.py?AlgorithmsAndSizesOfInstances" alt="" /> ]]] ********< ---- !! Send us a comment ... ''' <form action="https://www.solipsys.co.uk/cgi-bin/FormMail.pl" method=post> ''' <input type=hidden name="recipient" value="colinsblogcomment@solipsys.co.uk" > ''' <input type=hidden name="subject" value="Blog comment : AlgorithmsAndSizesOfInstances" > ''' <input type=hidden name="redirect" value="https://www.solipsys.co.uk/new/ThankYouForYourComment.html" > ''' <input type=hidden name="missing_fields_redirect" value="https://www.solipsys.co.uk/RequestError.html"> ''' <input type=hidden name="env_report" value="REMOTE_HOST, REMOTE_ADDR, HTTP_USER_AGENT" > ''' <input type=hidden name="print_blank_fields" value="1" > ********> width="47%" You can send us a message here. It doesn't get published, it just sends us an email, and is an easy way to ask any questions, or make any comments, without having to send a separate email. So just fill in the boxes and then ''' <font size="+4"><INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"></font> ******** width="53%" ********< ''' <table cellpadding="5"> ''' <tr> ''' <td valign="top">Your name </td> <td valign="top">:</td> ''' <td> <input type=text name="realname" size="48"> </td> ''' <tr> ''' <td valign="top">Email </td> <td valign="top">:</td> ''' <td> <input type=text name="email" size="48"> </td> ''' </tr> ''' <tr> ''' <td valign="top">Message </td> <td valign="top">:</td> ''' <td> <TEXTAREA NAME="Message" ROWS=10 COLS=64></TEXTAREA> </td> ''' </tr> ''' </table> ''' <center> ''' <font size="+4"> ''' <INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"> ''' </font> ''' </center> ''' </form> ********<