{"assignment":{"_schema_version":2,"course_id":37,"date_created":"2022-06-28T19:00:00+00:00","date_modified":"2025-11-17T16:25:34.838228+00:00","extra_instructor_files":"","extra_starting_files":"","forked_id":null,"forked_version":null,"hidden":false,"id":1135,"instructions":"## Questioning a Program\n\n- Is the program **correct**?\n- Is the program **readable**?\n- Is the program **fast**?\n\nEffective computer scientists try to make the best programs they can, and to do so they must ask reflective, critical questions about those programs.\nAlthough there are many kinds of questions to ask, the three most important criteria to ask about are: correctness, readability, and speed.\n\n## Critiera 1: Correctness\n\n* **Correctness**: Whether the program provides the appropriate output for all expected inputs.\n\nCorrectness is essential.\nAn incorrect program will not solve the problem it sets out to solve, and therefore is not useful.\nIn the context of coding, a problem is defined as the specification of the expected outputs for given inputs.\nThis is very similar to how we define functions and unit tests.\nFor example, a coding problem might ask you to \"define a function that consumes a list of integers and produces their sum\" or \"define a function that consumes a string and determines how often the character `\"X\"` appears.\" Unit tests can be used to determine if a program is incorrect, which is why we have spent so much time learning how to test programs.\n\n## Criteria 2: Readability\n\n* **Readability**: How understandable a program is for humans.\n\nReadability is also very important.\nPrograms usually end up being used for a long time, often longer than they are originally expected to last.\nPrograms created today might be used and extended for decades to come.\nThis is especially true for the massive programs that large teams of developers create together, like web browsers or office applications.\nThese programs will invariably have problems that need to be debugged, new features that must be added, and updates that will need to be made down the road.\nIf a program is not understandable, then the program will be difficult to improve and a lot of time will be wasted in the future.\nPoor variable names, unnecessarily long functions, and poor decomposition can seriously impede progress.\n\n## Criteria 3: Speed\n\n* **Speed**: How long a program takes to run.\n\nOur final question was \"how long does the program take to run?\", which is sometimes known as the _time complexity_ or _efficiency_ of a program.\nThis question is very important, but usually comes after the first two questions are answered.\nA fast program that doesn't work is not very useful, after all.\nStill, programs need to be fast enough to accomplish their goal and to respond to users' needs.\nThere is no single answer as to how fast a program needs to be\u2014the only answer is \"fast enough to get the job done.\" A lot of time is wasted by programmers trying to speed up a program when speed was not actually a problem.\nThat time that could have been spent improving correctness, making the program more readable, or working on other problems.\nHowever, before we can decide if a program is fast enough, we must have a way to determine how long a program takes to run.\n\n## The Length of a Program\n\n![A diagram showing how wall clock time is calculated.](bakery_time_complexity_wall_clock.png)\n\nThere are several obvious ways to measure the length of a program.\nAn incorrect way would be to measure the number of lines of code.\nWith `while` and `for` loops, we have seen how even just a few lines of code can do an awful lot of work.\nRelying on the number of lines of code as a measure of the length of a program is too limited.\n\nAn alternative approach that is much more helpful is to measure the amount of time the program takes to execute.\nImagine starting a watch when the program begins and then stopping the watch when it ends.\nYou take the difference between the two times, and that's the length of the program.\nThis is sometimes called the _wall clock time_.\nThis is more accurate but the downside is that we must sit and measure our running programs to understand how long they take.\n\n## Bigger and Bigger Data\n\n* Empty list (zero elements, tiny)\n* A list with one number (small)\n* Ten number list (still small)\n* One hundred elements (a little bigger)\n* A million elements (big)\n* A trillion elements (very big!)\n* ...\n\nPrograms are useful because they can be given different inputs each time the program is run and they will deliver the appropriate outputs.\nWith functions, for example, we can change the arguments as long as they still match the general type of parameters we specified.\nIntegers can have higher numbers, strings can have more characters, and lists can have more elements.\nThese different sizes of values reflect the size of the input.\nSometimes, the size of the input can have an impact on how long the program takes to execute.\nIf we are adding up the elements of a list, then having more elements to add will take more time.\nIn other words, the time of the program often has a relationship with the size of the input to the program.\n\n## Time as an Equation\n\n![A table with two columns, number of elements and running time, showing off the relationship between these two values.](bakery_time_complexity_table.png)\n\nA mathematical function establishes a relationship between one set of values and another set of values, somewhat like a programming function.\nThis mathematical function, or _equation_, can be determined by analyzing the trend over a bunch of example inputs and outputs.\nIn the table, we match the number of elements with the running time of the program that we measured.\nCareful analysis reveals that in this case, the relationship is that every new element takes 2 additional microseconds of work.\nThis is a time function and can help you make predictions about how your program would run for different sizes of input.\n\nOf course, in the real world, the trends are rarely so nice and neat.\nHow many datapoints do you need to accurately predict the future?\nThat is a very difficult question to answer.\nAny time you think you see a trend, the next data point might sink your hypothesis.\nIdeally, you would gather as much data as possible.\nUnfortunately, that is still very time consuming.\n\n## An Estimate\n\n* **Random-Access Machine (RAM) Model**: Estimate execution time based on common operations\n\nMeasuring the number of lines in a program is easy but very inaccurate.\nMeasuring the time taken with a watch is accurate but could take a long time.\nIf computer scientists had to sit and wait to check the runtime of every program they wrote, they would never get anything done.\nOne approach that acts as a middle path is to make an estimate of the time by tracing the program\u2014but with a simplified model of execution.\nComputer scientists have developed an approach called the Random-Access Machine Model that does exactly this.\n\n## The RAM Model\n\n* Assignment: One step\n* Printing: One step\n* Math/Logic Expression: One step\n* `if` statement: One step\n* `for` loop: _n_ steps\n* `while` loop: Varies\n* Function call: Varies\n\nIn the RAM Model, most simple actions such as assignment or printing take a single step.\nIn fact, all math and logic expressions take a single step, too, even if there are many operations inside of the expression.\nHowever, `for` and `while` loops are more complicated, as are function calls.\nThe `for` loop is not usually so bad, since it usually means that we just must do one additional step for each element of the input.\nBut with `while` loops and function calls, we cannot easily predict the time of the program.\nThis gets even more complicated when we start nesting functions inside of functions or loops inside of loops.\nBy counting the number of steps using this model, though, we can get an estimate of the program time without waiting around and can figure out a relatively accurate possible mathematical relationship.\nAlthough the RAM Model could be used to try and make exact time functions that precisely capture the number of steps in a program, computer scientists are usually fine with a rough estimate of the relationship.\n\n## Common Math Relationships\n\n- **Constant:** Input size does not affect runtime (simple math, accessing attribute in class)\n- **Linear:** Every additional input value leads to a constant amount of extra time (summing a list, filtering a list)\n- **Quadratic:** Every additional input value leads to a linear amount of extra time (nested list iteration)\n\nIn general, we will start off with three basic relationships.\nThere are many other kinds of relationships, one for each possible line you could see on a graph.\nBut for now, we want you to master these three.\n\nThe first is a _constant_ relationship, which is when there is no relationship at all between the size of the input and how long the program takes to run.\nThis is common for simple mathematics, accessing attributes in classes, and the actual step of starting a function call.\n\nThe next relationship is _linear_, where every additional input requires another single unit of time.\nThis happens easily with list operations, such as summing or filtering a list.\nLinear relationships take more time than constant but are usually still useful for most input sizes.\n\nThe last relationship we'll talk about here is _quadratic_, where the input size increasing means linearly increasing the time required for every element.\nWe see this when we are iterating through a square two-dimensional list.\nEach time we increase the size by one, we are really adding an entire row of elements\u2014not just a single element.\nQuadratic growth can get out of hand quite quickly and is usually not a good situation to be in.\nIdeally, our programs would be constant or linear time, but that is rarely the case for most interesting programs.\nSome problems inherently require quadratic time or possibly even larger relationships.\n\n## A Linear Example\n\n```python linear-example\ndef summate(values: str) -> int:\n    \"\"\" Add up all the numbers \"\"\"\n    numbers = values.split(\",\")\n    count = 0\n    for number in numbers:\n        total = total + int(number)\n    return total\n\n# 1 number, 1 iteration\nassert_equal(summate(\"5\"), 5)\n# 3 numbers, 3 iterations\nassert_equal(summate(\"1,2,3\"), 6)\n# 5 numbers, 5 iterations\nassert_equal(summate(\"2,2,2,2,2\"), 10)\n\n# N numbers, N iterations\nvalues = input(\"Enter comma-separated numbers:\")\nprint(summate(values))\n```\n\nLet's study some programs with different time relationships.\nIn this first example, the function `summate` will take in a comma-separated string of numbers and add the numbers together.\nFor the three test cases, we pass string literals and know exactly how many iterations there will be: one iteration for each number.\nFor the final call at the bottom, we do not know exactly how many numbers the user will enter, so we do not know how many iterations there will be.\nIt might be a few elements, or it might be a tremendous number of elements.\nEither way, that `for` loop is going to have to execute another assignment statement for each element that we have in the list.\nSo, in the end, we'll do a linear amount of work based on the input given by the user.\n\n## A Quadratic Example\n\n```python quadratic-example\ndef count_pairs_10(values: str) -> int:\n    \"\"\" Count pairs that add up to 10 \"\"\"\n    numbers = values.split(\",\")\n    pairs = 0\n    for number in numbers:\n        for other_number in numbers:\n            if number+other_number == 10:\n                pairs = pairs + 1\n    return pairs\n\n# 1 number, 1 iteration\nassert_equal(summate(\"3\"), 0)\n# 3 numbers, 9 iterations\nassert_equal(summate(\"1,4,6\"), 2)\n# 5 numbers, 25 iterations\nassert_equal(summate(\"1,4,6,8,9\"), 4)\n# N numbers, N*N iterations\nvalues = input(\"Enter comma-separated numbers:\")\nprint(count_pairs_10(values))\n```\n\nIn the next example, the function `count_pairs_10` also takes in a string of comma-separated numbers.\nInstead of just adding them up, the function uses a nested pair of `for` loops to iterate through each possible pair of numbers.\nIf the two numbers added together equal 10, then the `pairs` variable is incremented.\nEach number is eventually compared to every other number.\n\nAs an example, consider the test case `\"1,4,6\"`:\nIn the first iteration, the number `1` is compared against `1`, `4`, and `6` (but none equal `10`)\nOn the second iteration, the number `4` is compared against `1`, `4`, and `6` (and `4+6` make `10`)\nOn the third iteration, the number `6` is compared against `1`, `4`, and `6` (and `6+4` make `10`)\n\nSo, after the nine total iterations (`3*3`), the result is `2`.\nThe relationship between the number of elements in the string and the number of iterations is quadratic (a number raised to the power of two).\nSpecifically, for `n` elements, there will be `n*n` iterations (`n**2`).\n\n## Key Points about Time Complexity\n\n* Input size relates to program time.\n* Basic relationships are constant, linear, and quadratic.\n* The RAM Model can be used to estimate relationships.\n* Wall clock can be used to statistically determine relationships.\n\nWe are merely scratching the surface of the concept of _time_ _complexity_, and you will see this concept many more times on your journey to become a computer scientist.\nThere are also many more time relationships besides constant, linear, and quadratic.\nFor now, focus on understanding how different input sizes can lead to different runtimes.\nGet a handle on the relative sizes of the different relationships.\nYou can use the RAM model to estimate those relationships based on what the code does.\nAnd when in doubt, try running the program with different sizes and measure the speed to estimate the relationship yourself.\n\n## Summary\n\n- The three primary criteria to evaluate a program are:\n  - Correctness: Does the program return the correct value given a certain input?\n  - Readability: Is the program understandable to a human?\n  - Speed: How fast does the program take to execute?\n- Program speed is not necessarily related to the number of lines in the program but instead what the lines of code do.\n- A wall clock can be used to measure the execution time of a program.\n- Input size can be related to how long a program takes to execute.\n- Three basic time relationships are constant, linear, and quadratic (in descending order of speed).\n- The RAM Model can be used to estimate the relationship between the input size and the number of steps that the program will take to execute.\n\n","ip_ranges":"","name":"11A1) Time Complexity Reading","on_change":"","on_eval":"","on_run":"","owner_id":1,"owner_id__email":"acbart@udel.edu","points":0,"public":true,"reviewed":false,"sample_submissions":[],"settings":"{\n  \"header\": \"Time Complexity\",\n  \"youtube\": {\n    \"Bart\": \"ZTYq5nlvJaw\",\n    \"Amy\": \"Ct0eiVchytw\"\n  },\n  \"video\": {\n    \"Bart\": \"https://blockpy.cis.udel.edu/videos/bakery_time_complexity-Bart.mp4\",\n    \"Amy\": \"https://blockpy.cis.udel.edu/videos/bakery_time_complexity-Amy.mp4\"\n  },\n  \"summary\": \"\",\n  \"small_layout\": true\n}","starting_code":"","subordinate":true,"tags":[],"type":"reading","url":"bakery_time_complexity_read","version":15},"ip":"216.73.216.157","submission":{"_schema_version":3,"assignment_id":1135,"assignment_version":15,"attempts":0,"code":"","correct":false,"course_id":37,"date_created":"2026-05-20T18:20:14.369480+00:00","date_due":"","date_graded":"","date_locked":"","date_modified":"2026-05-20T18:20:14.369480+00:00","date_started":"","date_submitted":"","endpoint":"","extra_files":"","feedback":"","grading_status":"NotReady","id":2037064,"score":0.0,"submission_status":"Started","time_limit":"","url":"submission_url-55d33cb3-9eab-4677-b115-ffac85985ece","user_id":2044723,"user_id__email":"","version":0},"success":true}