educative.io

Multiplying polynomial and exponential complexities

Courses
,
#1

In big-O notation, when multiplying polynomial and exponential complexities, should we maintain the polynomial term in the product, or does the exponential term dominate in the product, prompting us to remove the polynomial?

In Matchsticks to Square, the provided time complexity is O(n*2^n), implying that we should maintain the polynomial.

In Sudoku, the problem prior, the provided time complexity is O(9^(nm)), which seems to exclude the (n+m) term in the product that we use in each frame to determine whether a move is valid, implying that we should exclude the polynomial from the final complexity class.

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Matchsticks to Square - Grokking Coding Interview Patterns in Python

#2

Hello @Isaac_Haseley,

For the matchsticks to square problem, both polynomial (e.g., n) and exponential (e.g., 2^n) terms in the complexity expression indicate that both factors influence the algorithm’s runtime. However, as n grows, the exponential term will dominate the runtime growth. Despite this, the polynomial term is still maintained in the expression (O(n*2^n)) to accurately reflect the algorithm’s behavior, particularly when the polynomial term has a significant impact on the runtime for values of n that are not extremely large.

In cases where the complexity is purely exponential, and there is no explicit mention of a polynomial term (like the Sudoku problem), where the complexity is O(9^(nm))), where n and m are puzzle dimensions, the polynomial term (n+m) is negligible because the constants n=9 and m=9 have minimal impact on the algorithm’s growth rate, resulting in the exclusion of the polynomial term from the final complexity analysis.

I hope this answers your query about the complexity analysis between both problems. Thanks!