Complexity

Question 1

Big O

Answer 1

• O(g(n)) is the set of functions are “upper-bounded” by g(n)
• If f(n) is a function that describes the running time of the program (w.r.t. input)
• Then f(n) is in O(g(n)) if g(n) dominates f(n) for some c after n₀
• Basically, f(n) will always be <= c*g(n)

Question 2

Big Omega

Answer 2

• Ω(g(n)) is the set of functions are “lower-bounded” by g(n)
• If f(n) is a function that describes the running time of the program (w.r.t. input)
• Then f(n) is in Ω(g(n)) if f(n) dominates g(n) for some c after n₀
• Basically, f(n) will always be >= c*g(n)

Question 3

Little O

Answer 3

• More restrictive version of big O
• o(g(n)) is the set of functions that are dominated by g(n) for all constants c after some n₀
• f(n) and g(n) can’t have the same dominant term (can’t both be squares or cubes, etc)

Question 4

Little Omega [ω]

Answer 4

• More restrictive version of big Ω
• ω(g(n)) is the set of functions that are dominate g(n) for all constants c after some n₀
• f(n) and g(n) can’t have the same dominant term (can’t both be squares or cubes, etc)

Question 5

Theta

Answer 5

• The set of functions for which g(n) is both an upper and lower bound
• Θ(g(n)) is the set of functions that are in both O(g(n)) and Ω(g(n))
• Provides a tight bound
• c₁*g(n) <= f(n) <= c₂*g(n)
  
  • f(n) is sandwiched between g(n) on both sides (albeit with different constants c₁ and c₂)
• Many functions do not have a simple Θ

Question 6

Big O

Formal Definition

Answer 6

f(n) is in the set O(g(n)) if and only if:

There exist positive constants c & N₀ s.t. for all n > N₀,

f(n) <= c*g(n)

Question 7

Asymptotic

Answer 7

• Basically, when n is really large

Question 8

Best Case/Worst Case

Answer 8

• Describes how running time changes based on the type of input
• A program has a different best case and worst case if running time differs depending on input
• Ex: an algorithm might have a constant running time when input is sorted (best case), but a quadratic running time when input is reversed (worst case)
• Best/worst/average case each have their own Big O and Big Omega

Question 9

Upper Bound/Lower Bound

Answer 9

• An upper bound of f(n) is any function g(n) that is >= f(n) asymptotically
• A function f(n) has multiple (infinite) upper bounds
• Ex:
  
  • n²/2 is an upper bound of n²
  • n³ is also an upper bound of n²
• Lower bound is basically the reverse
  
  • Any function g(n) <= f(n)

Question 10

Space Complexity

Answer 10

• The maximum amount of space required at any given time for an algorithm to complete its task
• Uses the same notation (Big O, Big Omega, etc) as time complexity
• Includes:

1. The input
2. Any auxiliary space
3. Space created in the stack (in recursive calls)

• But, in general, when discussing space complexity, we only care about aux space and stack space

Question 11

Amortized Analysis

Answer 11

• An alternative approach to calculating the worst-case running time
• Used when your algorithm has more than one operation, some are cheap and some are expensive
• Ex: “append” consists of both populating a cell and, occationally, resizing an array
• Provides an upper bound on a sequence of operations
• Unlike average case, can’t get a higher running time (on a sequence) by being “unluckly”
• Three approaches
  
  • aggregate method
  • accounting method
  • potential method

Question 12

Average Case

Answer 12

• The performance of an algorithm based on what input is “most likely” to look like
• Based on probability of likely inputs
• Often requires statistical analysis
• Has its own upper bound/lower bound

Question 13

Averaging Method

Answer 13

• The most common type of amortized analysis
• Basically, add up the cost of n operations, and divide by n

Question 14

Logarithms and Complexity

Answer 14

For an input size of n

• log₂(n) is the number of times you can divide n by 2 before n becomes a fraction (while n is >= 1)
• Number of “iterations/steps” to process all elements
• Ex: input of size 32 can be processed with 5 steps

Question 15

Recursion and Complexity

Answer 15

• Time complexity is number of recursive calls (size of recursion tree) * complexity of each recursive calls
• Ex: fibonacci has O(2ⁿ) recursive calls, each is constant
• Ex: mergesort as O(n) recursive calls, each of which is (on average) O(log₂(n))
• Space complexity is max height of stack (max height of tree) * aux space in each frame + maximum amount of space allocated by any individual call

Question 16

decision problems

Answer 16

• problems with yes/no answers

Question 17

P

Answer 17

• set of all decision problems that can be solved in polynomial time

Question 18

EXP

Answer 18

• the set of all decision problems solvable in exponential time
• exponential ⇒ 2^{n^c}

Question 19

R

Answer 19

• the set of all decision problems that can be solved in finite time
• things out of R are “unsolvable”

Question 20

NP

Answer 20

• non-deterministic polynomial
• the set of decision problems which aren’t necessarily solveable in P, but whose ‘yes’ solutions can be confirmed (probably via a different algorithm) in polynomial time
• or, the set of decision problems can be solved in poly time by a non-deterministic turing machine
• P is in NP

Question 21

turing machine

Answer 21

• a hypothetical computer model that is powerful enough to compute anything that is computable

Consists of:

• Aribtrarily long/endless line of tape
  
  • tape is divided into square
  • every square has a 1,0
  • long enough tape in either direction
  • equivalent to unlimited RAM
• A state variable
• Set of rules
  
  • Describes what to do given a state and value on tape
• Read-write head

Question 22

non-deterministic turing machine

Answer 22

• hypothetical computer that can perform multiple actions at once
• in essense, explores multiple “branches” in a decision problem simultaneously

Question 23

turing complete

Answer 23

• it can do everything that a turing machine can do

Question 24

halting problem

Answer 24

• the problem of determining, given an arbitrary computer program, whether or not it ever finishes running or loops forever
• not in R (unsolvable)

Question 25

P = NP

Answer 25

• open question of whether all problems in NP are also in P
• most people think P != NP

Question 26

reductions

Answer 26

• converting from one type of problem to another
• ex: converting from unweighted shortest paths to weighted shortest paths by giving all paths weight of 1
• if you reduce A ⇒ B, the B is at least as hard as A

Question 27

hardness

Answer 27

• basically refers to complexity (difficulty)
• also refers to the relationship between 2 problems
• a problem B is hard for A if A can be reduced to B
• therefore, a solution to B can be used to get a solution to A
• we use the solutions for “harder” problems to solve the easier problems
• generally reduce from easier problem to harder problem, or to a problem with equivalent hardness

Question 28

NP-hard

Answer 28

• at least as “hard” as any other NP problem
• every problem in NP can be reduced to it
• if we could solve an NP-hard problem, we could use it to solve other problems of equivalent or lesser hardness
• includes problems that are not in NP (problems in EXP or R)

Question 29

NP-complete

Answer 29

• the set of decision problems that are:

1. NP-hard
2. in NP (as opposed to EXP)