Algorithms Flashcards
What are Algorithms?
The fastest and most efficient set of steps to solve a problem.
How do you determine the necessary algorithm to use for a problem?
By breaking down the problem into steps and understanding the problem.
What are algorithms composed of?
A clear problem statement, expected input & expected output.
How do you measure the efficiency of an algorithm
Through calculating the Time & Space complexity
What is time complexity?
Simple the measure of how long an algorithm takes. Run or compute time.
What is space complexity?
A measure of how much memory was used in order to compute an algorithm.
What are the 3 cases to measure complexity against?
Best case, Average case, Worst case
The best case to test on is the worst case. What does “n” represent in the worst case?
The amount, length, or form of measure for a given input in an algorithm.
What is a linear algorithm?
An algorithm that executes steps that walks through a data structure/input in a sequential manner.
What is a binary algorithm?
An algorithm that executes steps within half of the data structure & continues to narrow down by half until a value is found.
What is “Big O”? (Upper bound)
A notation that represents the complexity of an Algorithm in the worst-case scenario
The O in “Big O” represents what?
Order of magnitude of complexity
The “(n)” is considered what?
The function of a size
Constant Time O(1) represents what?
The runtime per operation is the same no matter how large “n” or input data is.
O(log n) or O(ln n) represents what?
Logarithmic Runtime.
What is a Logarithmic Runtime (Sublinear)?
A runtime that is the inverse of exponentiation. When number of operations is logarithmic to the sample size (data).
What is a Linear Runtime? O(n)
An algorithm that sequentially (step by step) moves through the input size.
What is Quadratic Runtime? O(n2)
When an algorithm’s number of operation scales by n ^ 2 (input size squared) Big O of n squared
What is Cubic Runtime? O(n3)
When an algorithm’s operations time scales w/ the input size by n ^ 3
What is Quasilinear runtime? O(n log n)
Runs (log n) amount of operations per n or per input amount | Big O of n x log n
What makes you have a long runtime?
The higher the amount of operations executed per n or input data results in longer runtime.
What is Polynomial Runtime? O(n^k)
Means a runtime where its function of a size is squared, cubic or an exponent of some number.
Is a Polynomial Runtime considered efficient?
Yes
What are 2 bad runtime types?
Exponential Runtimes O(x^n)
Factorial Runtimes O(n!)
