Computational Complexity

Question 1

What is computational complexity

Answer 1

determines if an algorithm is feasible for a certain problem, as data size increases and allows comparison between two algorithms being used for the same problem

Question 2

time efficiency

Answer 2

how run time changes as the problem’s parameters and input increases in size

Question 3

what does n represent

Answer 3

the problem size (length of list/array)

Question 4

what does T(n) represent

Answer 4

amount of time it takes to execute problem size n
the equation represents if the algorithm is constant, linear, quadratic, exponential
this tells how time is proportional to the size of the list

Question 5

how do you get the equation for T(n)

Answer 5

by counting the # of operations an algorithm will need for problem size N
cannot get the exact formula, just general characteristics

Question 6

what is Big-O notation

Answer 6

mathematical notation for talking about general categories of notations
the characteristics of Big-O notation tell us whether the formula is quadratic, linear etc
O(1), O(n) etc

Question 7

How to get Big-O formula

Answer 7

from T(n), get the most dominate term and drop coefficient

Question 8

General rules

Answer 8

Rule 1 - straight-line code
Rule 2 - consecutive sections of code
Rule 3 - if statements
Rule 4 - simple loops

Question 9

Rule 1 - straight line code

Answer 9

• straight-line code has no function calls, not dependent on the size of the input
• constant-time operations O(1)
  EX. variable assignment, arithmetic, array access

Question 10

Rule 2 - consecutive sections of code

Answer 10

• where 1 bit of code runs, followed by a loop or another piece of code
• to get Big-O, find max O(n) of O(f(n) and O(g(n))

Question 11

Rule 3 - if statements

Answer 11

• find max of if and else statement
  EX. max(f(n) and g(n))
  nested loops require finding the complexity of inner loop * outer loop

Question 12

rule 4 - simple loops

Answer 12

The complexity of the loop body TIMES the number of iterations
EX. 2n*O(n^2) = O(n^3)
** repeating a constant number of times in a loop doesn’t change complexity **
** nested loops require the complexity of inner loop * complexity of outer loop **

Question 13

O(log n)

Answer 13

• decreasing iterations through the array consistently
  EX. n = n/2
  most efficient

Question 14

Attributes of algorithms

Answer 14

• solves computational problem
• ease of understanding
• efficiency
• elegance

Question 15

Comparing algorithms

Answer 15

• comparing attributes

- comparing time complexity best/worst/avg cases

Question 16

Best, worst, average complexity

Answer 16

Best - smallest amount (T(n) = 1)
Worst - greatest amount of work (T(n) = n)
Avg - likelihood of different scenarios occurring (T(n) = n/2)

Question 17

O(1)

Answer 17

constant time

- arithmetic, variable assignments, accessing an array

Question 18

O(n)

Answer 18

linear time

- proportional to the size of the list/array

Question 19

O(n^2)

Answer 19

quadratic

- nested loops, dependent on the size of the list/array

Question 20

O(log n)

Answer 20

• dividing the proportion of the array accessed each time
• efficient
• the base is what n size is divided by
  EX. O(log 2 n) O(log 3 n)

Question 21

O(2^n)

Answer 21

• grows fastest

- polynomial