{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

CS 4.4. (ALEVEL) - Classification of Algorithms Flashcards

(4 cards)

1
Q

Big O Notation

A
  • Complexity of an algorithm
  • Assumes worst case scenario
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Big O notation examples

A

Constant -> O(1) e.g. determining if no. is odd/even (time independent of input)

Logarithmic -> O(log n) e.g. binary search (halves no. of items each iteration)

Linear -> O(n) e.g. linear search (worst case scenario goes through each item)

Linear logarithmic -> O(n log(n)) e.g. Merge sort

Polynomial -> O(n^2) e.g. Bubble sort (loop inside a loop)

Polynomial -> O(n^3) e.g. Checking 3d coordinates (A loop inside a loop
inside a loop)

Exponential -> O(2^n) e.g. Recursively calculating Fibonacci no.s (Intractable)

Factorial -> O(n!) e..g Travelers problem (intractable)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

limits of Computation

A

Tractable - can be solved, have a polynomial / less time solution

intractable - can be solved, have a exponential/worse time complexity likely use heuristic method (approximations solutions to a problem)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Halting problem

A
  • determining when a program will halt without executing it for a given input
  • uncomputable (cannot be solves by computers)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly