BIG O NOTATION

Question 1

what is an assignment statement

Answer 1

any statement where a value is set or updated
- fewer assignment statements mean higher efficiency

Question 2

what is tractability

Answer 2

tractability refers to how feasible it is to solve a problem efficiently as the input size grows

• a function is tractable if it is polynomial time complexity or better

Question 3

best to worst functions

Answer 3

O(1) – Constant time
O(log n) – Logarithmic time
O(n) – Linear time
O(n log n) – Log-linear time
O(n^k) – Polynomial time
O(2ⁿ) – Exponential time
O(n!) – Factorial time

• last 2 are intractable

Question 4

rules for big O notation

Answer 4

1. Focus on the Largest Growing Term:
   
   • For the function f(n) = 5n^2 + 3n + 10, the dominant term is n ^2, so big O representation is is O(n²).
2. Ignore Constant Factors
   
   • f(n)=3n and f(n)=10n are both O(n)
3. Drop Lower-Order Terms
   
   • For f(n)=n^3+5n^2+20n, the cubic term grows fastest, so the complexity is O(n³)
4. Non-Dominant Operations
   If an algorithm contains several steps, the step with the highest complexity determines the overall Big O.

Question 5

what is big O notation

Answer 5

• a way to measure how the runtime or space requirements of an algorithm grow as the input size increases
• gives us an idea of how efficiently an algorithm performs when dealing with larger amounts of data.

Question 6

why do we use big O

Answer 6

• To understand the scalability of algorithms.
• To compare different algorithms based on their performance.
• To ensure that programs can handle larger datasets without becoming too slow.

Question 7

O(1) - Constant time complexity

Answer 7

• The algorithm’s runtime does not depend on the size of the input. It always takes the same amount of time.
• eg, Accessing an element from an array by its index.

Question 8

O(logn) - logarithmic time complexity

Answer 8

• The algorithm’s time grows logarithmically. As the input size increases, the time only increases slowly.
  eg - Binary search in a sorted array.

Question 9

O(n) - linear time complexity

Answer 9

• The runtime grows linearly with the size of the input.
• If the input doubles, the time taken also doubles.
  eg - iterating from 1 to a certain number

Question 10

O(n log n) - Linearithmic Time

Answer 10

• This is often seen in efficient sorting algorithms like merge sort or quicksort.
• The time grows faster than linear but slower than quadratic.

Question 11

O(n²) - Quadratic Time

Answer 11

• The runtime grows quadratically.
• If the input size doubles, the time taken grows by four times.
• Common in algorithms with nested loops.Example:
  A simple implementation of bubble sort.

Question 12

O(2^n) - Exponential Time

Answer 12

• The time grows exponentially
• The runtime doubles with each additional input
• Algorithms that involve recursive branching often have this complexity.
  eg - Solving the Fibonacci sequence recursively.

Question 13

O(n!) - Factorial Time

Answer 13

• The runtime grows factorially.
• Extremely slow for even moderate input sizes
• Common in algorithms that involve generating permutations
  eg - Solving the traveling salesman problem by brute force.

Question 14

time complexity for a hash table

Answer 14

Inserting, Deleting, and Searching: O(1)
- (O(n) in the worst case due to collisions)

Question 15

time complexity for an array

Answer 15

• Accessing an element by index: O(1)
• Searching for an element: O(n)
• Inserting an element at the end: O(1) (if there’s space)
• Inserting at the beginning: O(n)

Question 16

time complexity for queues and stacks

Answer 16

• Push (insert), Pop (remove): O(1)
• Access the top element: O(1)

Question 17

linked list time complexity

Answer 17

• Insertion and Deletion: O(1) (if we have a reference to the node)
• Searching for an element: O(n)

Question 18

binary tree time complexity

Answer 18

Searching, Insertion, and Deletion: O(log n) on average, but O(n) in the worst case (if the tree becomes unbalanced)

Question 19

time complexity for sorting algorithms

Answer 19

Bubble Sort: O(n²)
Merge Sort: O(n log n)
Quick Sort: O(n log n) on average (but O(n²) in the worst case)

Question 20

why is big O important

Answer 20

• Choosing Efficient Algorithms: Knowing the time complexity of an algorithm helps us choose the right one for large inputs.
  
  • eg : Merge Sort (O(n log n)) is more efficient for large datasets than Bubble Sort (O(n²)).
• Scalability: Algorithms with lower time complexities can handle larger data efficiently.
  
  • If you need to handle huge datasets, linear or logarithmic algorithms are preferable over quadratic or exponential ones.

-

Question 21

what is algorithmic complexity

Answer 21

How much time or resources an algorithm needs as the size of the input increases.

Question 22

what are hardware constraints

Answer 22

when the physical hardware of a computer can limit how fast or how much data can be processed.

Question 23

what is a tractable algorithm?

what is an intractable problem

Answer 23

A problem is called tractable if it can be solved in polynomial time or better

A problem is called intractable if it cannot be solved in polynomial time.

Question 24

example of an intractable problem

Answer 24

The Traveling Salesman Problem (TSP) – Given a set of cities and the distances between them, the problem is to find the shortest route that visits each city and returns to the starting point. The time complexity is O(n!), making it an intractable problem.

Question 25

how do people solve intractable problems

Answer 25

heuristic approaches

Question 26

what are undecidable algorithms

Answer 26

problems that simply cannot be solved by any algorithm, regardless of how fast or powerful our hardware is

Question 27

example of an undecidable algorithm

Answer 27

The Halting Problem – This problem asks whether a computer program will eventually stop running (halt) or continue forever for a given input.

Question 28

why is bubble sort o(n^2)

Answer 28

because it involves nested loops where each element is compared with others,
resulting in n comparisons for each of the n elements.

Question 29

what is a heuristic approach

Answer 29

a heuristic approach employs a method of finding a solution that may not be the best
eg an algorithm might consider visiting certain cells first

Question 30

why is merge sort n log n time complexity

Answer 30

because the list is divided in half log n times, and merging takes linear time, resulting in n log n operations.

Question 31

why is binary search log n

Answer 31

because each comparison halves the search space,

Question 32

why is iterating to a number n time complexity

Answer 32

because you have to check each element once in a linear scan.

Question 33

why is accessing an element 1 time complexity

Answer 33

because it’s a direct memory access based on index.