LN1 Algorithms in General and Time Complexity

Question 1

What is an algorithm in the context of computer science?

Answer 1

An algorithm is a precise and unambiguous set of instructions for performing calculations to solve a specific problem for every possible input instance. It is an abstract mathematical concept, independent of any programming language or machine implementation.

Question 2

Define the terms “problem” and “instance” in algorithm design.

Answer 2

A “problem” is a general question to be solved, defined by a set of possible inputs and the desired output for each input. An “instance” is a specific input from the set of possible inputs for the problem.

Question 3

Why is an algorithm not the same as a computer program?

Answer 3

An algorithm is an abstract concept outlining the steps to solve a problem, while a program is a concrete implementation of an algorithm in a specific programming language, complete with syntax and language-specific structures.

Question 4

What is the importance of distinguishing between algorithms and programs?

Answer 4

Distinguishing between algorithms and programs allows for focusing on the problem-solving process without being distracted by programming details. It enables the design of efficient algorithms that can be implemented in any programming language.

Question 5

Why should algorithm development come before programming?

Answer 5

Developing the algorithm first ensures a correct and efficient solution to the problem. Programming without a well-designed algorithm may lead to inefficient or incorrect solutions, as implementation details can distract from underlying problem-solving.

Question 6

What are elementary operations in time complexity analysis?

Answer 6

Elementary operations are the basic computations that an algorithm performs, considered to take constant time. Examples include arithmetic operations on single digits, comparisons, and data access operations.

Question 7

How is the size of an instance defined in algorithm analysis?

Answer 7

The size of an instance, denoted as n, is typically defined as the amount of input data, such as the number of elements in a list, the number of vertices in a graph, or the number of digits in a number.

Question 8

What is time complexity and why is it crucial in algorithm analysis?

Answer 8

Time complexity measures the amount of computational time an algorithm takes relative to the size of the input. It is crucial because it helps predict performance and scalability, guiding the selection of the most efficient algorithm for a problem.

Question 9

What is Big-O notation?

Answer 9

Big-O notation describes an upper bound on the time complexity of an algorithm, characterizing its growth rate by focusing on the dominant term and ignoring constant factors and lower-order terms.

Question 10

How do you formally define that a function t(n) is O(f(n))?

Answer 10

A function t(n) is O(f(n)) if there exists a positive constant c and a value n₀ such that for all n ≥ n₀, t(n) ≤ c * f(n). This means t(n) does not grow faster than f(n) up to a constant multiple.

Question 11

Why are constants and lower-order terms ignored in Big-O notation?

Answer 11

Constants and lower-order terms become negligible for large input sizes compared to the dominant term, so Big-O notation focuses on the most significant factor affecting growth rate.

Question 12

Explain the difference in time complexity between adding and multiplying two n-digit numbers.

Answer 12

Adding two n-digit numbers has a time complexity of O(n) because each digit is processed once. Multiplying two n-digit numbers using the standard algorithm has a time complexity of O(n²) because each digit of one number is multiplied by each digit of the other.

Question 13

Is it possible to multiply two n-digit numbers faster than O(n²)?

Answer 13

Yes, advanced algorithms like Karatsuba’s algorithm and the Fast Fourier Transform (FFT) based algorithms achieve multiplication in O(n^1.585) and O(n log n log log n) time, respectively.

Question 14

What is the Interval Scheduling problem?

Answer 14

The Interval Scheduling problem involves selecting the maximum number of non-overlapping intervals from a given set of intervals on the real axis.

Question 15

How does the Big-O notation handle the sum of two functions?

Answer 15

The Big-O of a sum of functions is determined by the function with the largest growth rate. Formally, O(f(n) + g(n)) = O(max(f(n), g(n))).

Question 16

What does it mean when we say an algorithm has polynomial time complexity?

Answer 16

An algorithm has polynomial time complexity if its running time can be expressed as O(n^k) for some constant k, meaning it scales reasonably with input size and is considered efficient.

Question 17

Can you give an example of an algorithm with logarithmic time complexity?

Answer 17

Binary search is an example of an algorithm with logarithmic time complexity, specifically O(log n), as it divides the search interval in half with each step.

Question 18

How does Big-O notation compare the growth rates of n^c and a^n for constants c > 0 and a > 1?

Answer 18

Exponential functions a^n grow faster than any polynomial n^c, so n^c = o(a^n), meaning n^c grows significantly slower than a^n.

Question 19

What is the significance of logarithmic functions in algorithm analysis?

Answer 19

Logarithmic functions often appear in time complexities of algorithms that divide the problem size by a constant factor at each step, such as divide-and-conquer algorithms.

Question 20

Is it correct to say O(n log n) = O(n) because log n grows slowly compared to n?

Answer 20

No, this is incorrect. While log n grows slowly, it is not negligible, and O(n log n) represents a higher growth rate than O(n).

Question 21

Does the base of the logarithm matter in Big-O notation?

Answer 21

No, the base of the logarithm does not affect Big-O notation because logarithms with different bases differ by a constant factor, which is ignored in Big-O analysis.

Question 22

What is an example where worst-case time complexity is too pessimistic?

Answer 22

Quicksort has a worst-case time complexity of O(n²) but an average-case time complexity of O(n log n). In practice, the average-case is more representative, making worst-case analysis too pessimistic for this algorithm.

Question 23

How does O(n + n/2 + n/4 + n/8 + …) simplify to O(n)?

Answer 23

The sum forms a geometric series that converges to 2n, so the total complexity is O(n), as the series sums to a constant multiple of n.

Question 24

Why might we allow exceptions in the definition of Big-O notation?

Answer 24

Allowing finite exceptions simplifies analysis by focusing on large n behavior without worrying about small input sizes where the inequality might not hold.

Question 25

Can we say that O(n + … + n) = O(n) regardless of the number of terms?

Answer 25

No, the total complexity depends on the number of terms. If there are k terms, the complexity is O(k * n). Only if k is a constant does it simplify to O(n).

Question 26

Is O(n log n) in O(n log log n), and vice versa?

Answer 26

No, n log n grows faster than n log log n, so O(n log log n) ⊆ O(n log n), but not the other way around.

Question 27

How do we use limits to prove O-bounds?

Answer 27

If the limit of t(n)/f(n) as n approaches infinity is a constant c ≥ 0, then t(n) = O(f(n)).

Question 28

What is the practical implication of an algorithm with exponential time complexity?

Answer 28

Algorithms with exponential time complexities (like O(2^n)) become impractical for even moderately large input sizes due to the rapid growth in running time.

Question 29

How can we show that O(n^√n) = O(2^n)?

Answer 29

Since n^√n = e^(√n * ln n), and √n * ln n grows slower than n, n^√n grows slower than any exponential function like 2^n, so O(n^√n) ⊆ O(2^n).

Question 30

Why are polynomial time algorithms considered efficient?

Answer 30

Because their running times increase at a manageable rate as input size grows, making them practical for a wide range of problem sizes.

Question 31

Explain why algorithms with time complexities of O(n log n) are generally preferable to those with O(n²).

Answer 31

Because n log n grows significantly slower than n², especially for large n, resulting in faster algorithms that scale better with increased input sizes.

Question 32

Why is average-case analysis sometimes more appropriate than worst-case?

Answer 32

In cases where worst-case scenarios are rare or artificial, average-case analysis provides a more realistic measure of an algorithm’s performance on typical inputs.

Question 33

What is a practical example of logarithmic time complexity in data structures?

Answer 33

Operations on balanced binary search trees (e.g., insertion, deletion, search) typically have O(log n) time complexity due to the tree’s height being logarithmic in the number of nodes.

Question 34

How does understanding Big-O notation help in algorithm design?

Answer 34

It helps in evaluating and comparing algorithms based on their efficiency and scalability, guiding the selection of the most appropriate algorithm for a given problem.

Question 35

What does it mean for one function to be “smaller” than another in terms of Big-O notation?

Answer 35

It means that the first function grows at a slower rate than the second function as the input size increases.

Question 36

Can an algorithm with a higher Big-O classification be faster in practice than one with a lower one?

Answer 36

Yes, for small input sizes or due to large constant factors in the lower Big-O algorithm, but for large inputs, the algorithm with the lower Big-O classification will generally be faster.

Question 37

Why is Big-O notation considered an “asymptotic” analysis?

Answer 37

Because it describes the behavior of functions as the input size approaches infinity, focusing on long-term growth rates rather than exact values for finite n.

Question 38

In the context of Big-O notation, what does “suppressing constant factors” mean?

Answer 38

It means ignoring multiplicative constants in the analysis since they do not affect the overall growth rate and are insignificant for large input sizes.