ITA - Week 3

Question 1

What are the approaches to analyse Time Complexity

Answer 1

Theoretical Analysis and Empirical Analysis

Question 2

What is Theoretical Analysis

Answer 2

Study the number of times the algorithm performs some basic operations

Question 3

What is Empirical Analysis

Answer 3

Code and run the algorithm on a computer for some inputs and measure how long it takes

Question 4

What are the disadvantages of empirical analysis

Answer 4

Depends on speed of computer
Wastes time to code solution if algorithm is slow
Can’t try all inputs

Question 5

How is efficiency measured

Answer 5

Basic operations and input size

Question 6

How is the size of an input determined for a list input

Answer 6

The number of elements in the list

Question 7

What is log2^x

Answer 7

x

Question 8

What will log n refer to

Answer 8

log base2 n

Question 9

log2(x*y) = ?

Answer 9

log2 x + log2 y

Question 10

log2(x/y) = ?

Answer 10

log2 x - log2 y

Question 11

log2(x^y) = ?

Answer 11

y * log2 x

Question 12

What is A for a given algorithm

Answer 12

Worst case efficiency - Max running time
Best case - Min running time
Average case - Avg running time

Question 13

The average case is the average of the best and worst case. True or False?

Answer 13

False

Question 14

When is binary searching used instead of sequential searching

Answer 14

When a list is pre-sorted, as it is more efficient

Question 15

What is the idea of a binary search

Answer 15

Compare k with middle element

If k is smaller than the middle, focus only of the first half and vice versa

Question 16

Important functions

Answer 16

1 - constant
loga n - logarithmic
n, n^2… - polynomial
2^n - exponential

Question 17

What is Big-O notation

Answer 17

A way of comparing functions that ignores constant factors and small input sizes

Question 18

What is f(n) = O(g(n)) read as

Answer 18

f(n) is of order g(n)

Question 19

Big-O notation approximations

Answer 19

2n & n
n & n+1
n^2 +n & n^2

Question 20

Big-O hierarchy (lowest to highest)

Answer 20

log n < log^2 n < sqrt(n) < n < nlog n < n^2 < 2^n

Question 21

Big-O formal definition

Answer 21

f(n) exists in O(g(n)) if there exists constants c>0 and n0>0, such that f(n) eqg c . g(n) for all n>n0

Question 22

eqg meaning

Answer 22

Equal to or greater than