BigO

Question 1

What are the four most common functions used on data structures. These are also the four criteria used by BigO notation to score efficiency.

Answer 1

1. Accessing elements
2. Searching for an element
3. Inserting an element.
4. Deleting an element.

Question 2

BigO allows us to create a ‘report card’ based on the four criteria. This allows us to know what a certain data structure is…

Answer 2

Good at,
Bad at, and
When it should be used

Question 3

What is the equation is used by BigO to calculate a functionality’s score in each of the four areas?

Answer 3

The Time Complexity equation.

Question 4

How does a Time Complexity equation work?

Answer 4

By inserting the size of the data-set as an integer (n), and retuning the number of operations that need to be conducted by the computer before the function can finish.

Question 5

What is the N value in BigO?

Answer 5

N is the size of the data set. (The amount of elements contained within the data structure)

Question 6

When judging data structures, which scenario do we always use…

Answer 6

The worst case scenario. I.e. The longest time it could possibly take. E.g. The item we are searching for in an array is in the last possible location we attempt to check.

Question 7

Why is it called BigO notation?

Answer 7

Because the function is represented by a big ‘O’ followed by a set of parentheses. E.g. O()

Question 8

How do we pronounce the following…
O(2),
O(5)

Answer 8

O of 2
O of 5
O being pronounced “oh” like the letter, and NOT zero.

Question 9

What does O(7) mean?

Answer 9

It takes 7 operations of the computer before our function can finish.

Question 10

O(4) is an example of Constant Time. What does constant time mean?

Answer 10

No matter the size of our data set, it will always take the same amount of time to run. These arent very common though, as most of the time, our integer (n), is going to have some adverse effect on how many operations it takes.

Question 11

Why does BigO measure efficiency in terms of number of operations and not time?

Answer 11

Because measuring by time is biased towards better hardware. Number of operations levels the playing field.

Question 12

BigO isn’t the only input you should consider when deciding which data structure to implement in your program … Why?

Answer 12

Many data structures have specific quirks or features which separate them from the rest and may provide additional functionality that make them extremely useful.

Question 13

What are the 7 most common Time Complexity equations, from most efficient to least efficient? Also which are considered Good and which bad?

Answer 13

O(1) GOOD, 
O(log n) GOOD,
O(n) GOOD,
O(n log n) BAD,
O(n^2), n to the power of 2, BAD, 
O(2^n) 2 to the power of n, BAD
O(n!), n Factorial, VERY BAD

Question 14

What is the absolute best “score” a data structure can achieve?

Answer 14

O(1)

This means no matter what the size of the data set is, the task will be completed in a single instruction.

Question 15

When is O(log n) most efficient?

Answer 15

When the data set size increases. Its efficiency slope decreases when n increases.
Think BinarySearch, for an n of 10 the first operation cuts it by half ruling out 5 elements, whereas for an n of 1,000,000 the first operation cuts it by half ruling out 500,000 elements!

Question 16

Give an example of an O(1) operation.

Answer 16

Array access with index.

Question 17

Give an example of an O(log n) operation.

Answer 17

A BinarySearch on a sorted list.

Question 18

Give an example of an O(n) operation.

Answer 18

Array linear search when data is unsorted. Array inserts and deletes.

Question 19

Name the 3 “GOOD” equations.

Answer 19

1. O(1)
2. O(log n)
3. O(n)

Question 20

Name the 3 “BAD” equations.

Answer 20

1. O(n log n)
2. O(n^2)
3. O(2^n)

Question 21

How does O(n log n) perform as the data-set size (n) increases?

Answer 21

I becomes more INEFFICIENT as n increases. Its efficiency slope increases when n increases.

Question 22

Which two equations are exponential?

Answer 22

1. O(n^2)

2. (2^n)

Question 23

Why are exponential equations very bad?

Answer 23

The larger the data-set you have, the more inefficient they become.