{"action":"created","comment":{"url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/comments/85291626","pull_request_review_id":6012443,"id":85291626,"diff_hunk":"@@ -0,0 +1,24 @@\n+>>> Worksheet C: Computational Complexity\n+\n+A)\tThe algorithm performs a check for duplications in a list, with n being the length of the list. If a duplication is found then the procedure returns True, if no duplications are found in list then the procedure returns False.\n+\n+B)\tThe worst case running time is quadratic O(N)² because the program has a for loop nested within the first for loop and therefore, the amount of iterations needed increases by the square of the input size. The program would have been linear had the second list not been nested in the first, and adding a new loop would increase the number of iterations proportionally. However, with this quadratic algorithm, if n = 6, for every iteration of the first loop, the inner loop will perform 6 loops: with each increase of the input, the loops on the second iteration will be n².\n+\n+C)\tThe algorithm is still correct; the procedure now only runs through j as far as i – 1. The procedure will only check a value against values that came before it in the list. This stops the procedure from checking a value against the same value multiple times and stops a value being checked against itself.\n+\n+D)\tThe algorithm will run approximately twice as fast because the procedure no longer needs to perform as many iterations. The procedure no longer checks the same two values against each other more than once and no longer checks a value against itself. Overall this roughly halves the number of iterations.\n+\n+E) The time complexity is still quadratic as doubling n would roughly quadruple the amount of iterations required.\n+\n+F)\tThe time complexity of Python’s built-in [1] SORT () function is O (n log n).","path":"worksheet_C/README.md","position":13,"original_position":13,"commit_id":"86bf60c2e115ff28e111830034c7e47c37443851","original_commit_id":"86bf60c2e115ff28e111830034c7e47c37443851","user":{"login":"edpowley","id":4038033,"avatar_url":"https://avatars.githubusercontent.com/u/4038033?v=3","gravatar_id":"","url":"https://api.github.com/users/edpowley","html_url":"https://github.com/edpowley","followers_url":"https://api.github.com/users/edpowley/followers","following_url":"https://api.github.com/users/edpowley/following{/other_user}","gists_url":"https://api.github.com/users/edpowley/gists{/gist_id}","starred_url":"https://api.github.com/users/edpowley/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edpowley/subscriptions","organizations_url":"https://api.github.com/users/edpowley/orgs","repos_url":"https://api.github.com/users/edpowley/repos","events_url":"https://api.github.com/users/edpowley/events{/privacy}","received_events_url":"https://api.github.com/users/edpowley/received_events","type":"User","site_admin":false},"body":"✅ but a better source would be e.g. the official Python documentation wiki -- this source appears to be a set of lecture notes, which are generally not an authoritative source","created_at":"2016-10-27T08:45:05Z","updated_at":"2016-10-27T08:46:47Z","html_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets/pull/34#discussion_r85291626","pull_request_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34","_links":{"self":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/comments/85291626"},"html":{"href":"https://github.com/Falmouth-Games-Academy/comp110-worksheets/pull/34#discussion_r85291626"},"pull_request":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34"}}},"pull_request":{"url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34","id":88638875,"html_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets/pull/34","diff_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets/pull/34.diff","patch_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets/pull/34.patch","issue_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues/34","number":34,"state":"open","locked":false,"title":"Worksheet B Submission","user":{"login":"hannahlu","id":22060783,"avatar_url":"https://avatars.githubusercontent.com/u/22060783?v=3","gravatar_id":"","url":"https://api.github.com/users/hannahlu","html_url":"https://github.com/hannahlu","followers_url":"https://api.github.com/users/hannahlu/followers","following_url":"https://api.github.com/users/hannahlu/following{/other_user}","gists_url":"https://api.github.com/users/hannahlu/gists{/gist_id}","starred_url":"https://api.github.com/users/hannahlu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hannahlu/subscriptions","organizations_url":"https://api.github.com/users/hannahlu/orgs","repos_url":"https://api.github.com/users/hannahlu/repos","events_url":"https://api.github.com/users/hannahlu/events{/privacy}","received_events_url":"https://api.github.com/users/hannahlu/received_events","type":"User","site_admin":false},"body":"","created_at":"2016-10-10T10:19:02Z","updated_at":"2016-10-27T08:46:47Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b3791a9e886885684aec9a8544dc4bac8cc91c25","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34/commits","review_comments_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34/comments","review_comment_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/comments{/number}","comments_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues/34/comments","statuses_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/statuses/86bf60c2e115ff28e111830034c7e47c37443851","head":{"label":"hannahlu:master","ref":"master","sha":"86bf60c2e115ff28e111830034c7e47c37443851","user":{"login":"hannahlu","id":22060783,"avatar_url":"https://avatars.githubusercontent.com/u/22060783?v=3","gravatar_id":"","url":"https://api.github.com/users/hannahlu","html_url":"https://github.com/hannahlu","followers_url":"https://api.github.com/users/hannahlu/followers","following_url":"https://api.github.com/users/hannahlu/following{/other_user}","gists_url":"https://api.github.com/users/hannahlu/gists{/gist_id}","starred_url":"https://api.github.com/users/hannahlu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hannahlu/subscriptions","organizations_url":"https://api.github.com/users/hannahlu/orgs","repos_url":"https://api.github.com/users/hannahlu/repos","events_url":"https://api.github.com/users/hannahlu/events{/privacy}","received_events_url":"https://api.github.com/users/hannahlu/received_events","type":"User","site_admin":false},"repo":{"id":68899232,"name":"comp110-worksheets","full_name":"hannahlu/comp110-worksheets","owner":{"login":"hannahlu","id":22060783,"avatar_url":"https://avatars.githubusercontent.com/u/22060783?v=3","gravatar_id":"","url":"https://api.github.com/users/hannahlu","html_url":"https://github.com/hannahlu","followers_url":"https://api.github.com/users/hannahlu/followers","following_url":"https://api.github.com/users/hannahlu/following{/other_user}","gists_url":"https://api.github.com/users/hannahlu/gists{/gist_id}","starred_url":"https://api.github.com/users/hannahlu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hannahlu/subscriptions","organizations_url":"https://api.github.com/users/hannahlu/orgs","repos_url":"https://api.github.com/users/hannahlu/repos","events_url":"https://api.github.com/users/hannahlu/events{/privacy}","received_events_url":"https://api.github.com/users/hannahlu/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/hannahlu/comp110-worksheets","description":"Reflecting on programming and the principles of computing, in addition to learning how to annotate source code.","fork":true,"url":"https://api.github.com/repos/hannahlu/comp110-worksheets","forks_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/forks","keys_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/keys{/key_id}","collaborators_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/teams","hooks_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/hooks","issue_events_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/issues/events{/number}","events_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/events","assignees_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/assignees{/user}","branches_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/branches{/branch}","tags_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/tags","blobs_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/git/refs{/sha}","trees_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/git/trees{/sha}","statuses_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/statuses/{sha}","languages_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/languages","stargazers_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/stargazers","contributors_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/contributors","subscribers_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/subscribers","subscription_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/subscription","commits_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/commits{/sha}","git_commits_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/git/commits{/sha}","comments_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/comments{/number}","issue_comment_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/issues/comments{/number}","contents_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/contents/{+path}","compare_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/compare/{base}...{head}","merges_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/merges","archive_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/downloads","issues_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/issues{/number}","pulls_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/pulls{/number}","milestones_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/milestones{/number}","notifications_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/labels{/name}","releases_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/releases{/id}","deployments_url":"https://api.github.com/repos/hannahlu/comp110-worksheets/deployments","created_at":"2016-09-22T08:08:19Z","updated_at":"2016-10-22T10:06:30Z","pushed_at":"2016-10-23T23:08:11Z","git_url":"git://github.com/hannahlu/comp110-worksheets.git","ssh_url":"git@github.com:hannahlu/comp110-worksheets.git","clone_url":"https://github.com/hannahlu/comp110-worksheets.git","svn_url":"https://github.com/hannahlu/comp110-worksheets","homepage":"","size":8269,"stargazers_count":0,"watchers_count":0,"language":null,"has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"Falmouth-Games-Academy:master","ref":"master","sha":"2154a5a6f8d28997ab86fb60c97fd10cbb1e8a28","user":{"login":"Falmouth-Games-Academy","id":13518108,"avatar_url":"https://avatars.githubusercontent.com/u/13518108?v=3","gravatar_id":"","url":"https://api.github.com/users/Falmouth-Games-Academy","html_url":"https://github.com/Falmouth-Games-Academy","followers_url":"https://api.github.com/users/Falmouth-Games-Academy/followers","following_url":"https://api.github.com/users/Falmouth-Games-Academy/following{/other_user}","gists_url":"https://api.github.com/users/Falmouth-Games-Academy/gists{/gist_id}","starred_url":"https://api.github.com/users/Falmouth-Games-Academy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Falmouth-Games-Academy/subscriptions","organizations_url":"https://api.github.com/users/Falmouth-Games-Academy/orgs","repos_url":"https://api.github.com/users/Falmouth-Games-Academy/repos","events_url":"https://api.github.com/users/Falmouth-Games-Academy/events{/privacy}","received_events_url":"https://api.github.com/users/Falmouth-Games-Academy/received_events","type":"Organization","site_admin":false},"repo":{"id":43419657,"name":"comp110-worksheets","full_name":"Falmouth-Games-Academy/comp110-worksheets","owner":{"login":"Falmouth-Games-Academy","id":13518108,"avatar_url":"https://avatars.githubusercontent.com/u/13518108?v=3","gravatar_id":"","url":"https://api.github.com/users/Falmouth-Games-Academy","html_url":"https://github.com/Falmouth-Games-Academy","followers_url":"https://api.github.com/users/Falmouth-Games-Academy/followers","following_url":"https://api.github.com/users/Falmouth-Games-Academy/following{/other_user}","gists_url":"https://api.github.com/users/Falmouth-Games-Academy/gists{/gist_id}","starred_url":"https://api.github.com/users/Falmouth-Games-Academy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Falmouth-Games-Academy/subscriptions","organizations_url":"https://api.github.com/users/Falmouth-Games-Academy/orgs","repos_url":"https://api.github.com/users/Falmouth-Games-Academy/repos","events_url":"https://api.github.com/users/Falmouth-Games-Academy/events{/privacy}","received_events_url":"https://api.github.com/users/Falmouth-Games-Academy/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets","description":"Reflecting on programming and the principles of computing, in addition to learning how to annotate source code.","fork":false,"url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets","forks_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/forks","keys_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/teams","hooks_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/hooks","issue_events_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues/events{/number}","events_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/events","assignees_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/assignees{/user}","branches_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/branches{/branch}","tags_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/tags","blobs_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/git/refs{/sha}","trees_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/statuses/{sha}","languages_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/languages","stargazers_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/stargazers","contributors_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/contributors","subscribers_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/subscribers","subscription_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/subscription","commits_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/commits{/sha}","git_commits_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/git/commits{/sha}","comments_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/comments{/number}","issue_comment_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues/comments{/number}","contents_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/contents/{+path}","compare_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/merges","archive_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/downloads","issues_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues{/number}","pulls_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls{/number}","milestones_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/milestones{/number}","notifications_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/labels{/name}","releases_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/releases{/id}","deployments_url":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/deployments","created_at":"2015-09-30T07:54:37Z","updated_at":"2016-09-17T17:21:21Z","pushed_at":"2016-10-24T10:33:09Z","git_url":"git://github.com/Falmouth-Games-Academy/comp110-worksheets.git","ssh_url":"git@github.com:Falmouth-Games-Academy/comp110-worksheets.git","clone_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets.git","svn_url":"https://github.com/Falmouth-Games-Academy/comp110-worksheets","homepage":"","size":167385,"stargazers_count":0,"watchers_count":0,"language":null,"has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":37,"mirror_url":null,"open_issues_count":15,"forks":37,"open_issues":15,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34"},"html":{"href":"https://github.com/Falmouth-Games-Academy/comp110-worksheets/pull/34"},"issue":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues/34"},"comments":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/issues/34/comments"},"review_comments":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34/comments"},"review_comment":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/pulls/34/commits"},"statuses":{"href":"https://api.github.com/repos/Falmouth-Games-Academy/comp110-worksheets/statuses/86bf60c2e115ff28e111830034c7e47c37443851"}}}}
{"actor":{"display_login":"edpowley"}}