DSA - MATHS & COMPLEXITY

Question 1

What is the time complexity for a loop?

Answer 1

O(n)

Question 2

What is the time complexity for a nested loop?

Answer 2

O(n^2)

Question 3

What is worst case for Linear search

Answer 3

O(n)

Question 4

Why is Maths Good for Complexity Analysis?

Answer 4

Needs to check whether the choice ADTs is correct one for the chosen for the task or program

Question 5

What Does 2^10 equal? & Why is it useful?

Answer 5

-1024
- Useful when calculating greater powers like 2^50

Question 6

Define Log;

Answer 6

log_a(b) is the number you have to raise a to in order to get to b

Question 7

What are the 2 Dimensions we might be interested in?

Answer 7

TIME & SPACE

Question 8

What is TIME Performance?

Answer 8

How Long the algorithm takes to run?

Measure it in the number of Steps, due to normal time units depend on machine its on

Question 9

What is SPACE Performance?

Answer 9

How much memory it requires?

Different algorithms to accomplish the same task may use different amounts of memory.

Question 10

Define Big O:

Answer 10

f(n) = O(g(n))
=> g is an upper bound on how fast f grows as n increases
=> Only refer to relative growth.
How fast f grows in respect to how fast g grows

==> |f(n)| ≤ |Cg(n)|
where C is constant and n> n_0

Question 11

Define little o:

Answer 11

f(n) = o(g(n))
=> A Stricter Upper Bound than BIG O

Question 12

Define Theta:

Answer 12

f(n) = θ(g(n))
=> Provides both Upper bound and Lower bounds, which
are given as the same function but with different
constants

=> f & g grow at same rate
=> More precise than BIG O & little o
=> Tighter range of speeds for complexity
=> Bounded ABOVE but also BELOW x

==> C_1g(n) ≤ f(n) ≤ C_2g(n)
for positive constants of C_1, n_0& C_2, where n>n_0

=> f & g have the same rates of growth, with some constant
multiple
=> ONLY true if f(n) = O(g(n)) & g(n) = O(f(n))

Question 13

Define Asymptotically Equal:

Answer 13

f(n) ~ g(n)
=> Stricter Upper and Lower Bounds
=> f’(n) = g’(n)
=> One grows faster the other would grow to 0 or ∞

Question 14

Define Omega:

Answer 14

f(n)= Ω(g(n))
=> a Lower bound on how fast f grown as n increases
=> ONLY Lower bound of θ
=> Lower bound equivalent Big O
=> As f grows it will always grow at least at same rate as g
and CAN grow Faster

==> |f(n)|≥ |Cg(n)|
for a +ve C, n_0, where n>n_0

Question 15

Average Case Complexity:

Answer 15

Average complexity overall all possible inputs

Question 16

Define the Worst case time complexity?

Answer 16

• Case that will take the largest number of steps
• Max Time Taken => ideal for real-time situations to check if
  algorithm is suited
• Worst case Tends to be Average case
• Worst case analysis in real-time must be checked to see if it
  can still react quickly for highly critical scenarios.

Question 17

Define the Best Case Time Complexity?

Answer 17

• Shortest Possible Time
• Only when a Particular scenario or Case attempt
• Ideal complexity for Algorithm
• Companies want their algorithms to be better than everyone
  else

Question 18

Define the Average Case Time Complexity?

Answer 18

• Consider case every possible case for an input of size n and
  calculate the Average
• Tends to the complexity the algorithm will usually work at

ASSUME EACH CASE IS EQUALLY LIKELY