Picky questions about Big-O problem (Solution included).

  • Thread starter Thread starter s3a
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the nuances of Big-O notation, specifically the constants c and n_0 in algorithm analysis. Participants clarify that both constants must be greater than 0 for the notation to be valid, although c can technically be any real number, including 0, in certain contexts. A typo regarding the exponent in the expression cn^(1.5) is also noted, with a suggestion that it should be cn^(2.5). The consensus is that the problem statement is incomplete due to the lack of restrictions on c and the absence of absolute values.

PREREQUISITES
  • Understanding of Big-O notation and its application in algorithm analysis.
  • Familiarity with constants in mathematical expressions.
  • Basic knowledge of natural numbers and their properties.
  • Ability to identify and correct typographical errors in mathematical contexts.
NEXT STEPS
  • Research the formal definition of Big-O notation and its implications in algorithm complexity.
  • Study the role of constants in mathematical inequalities and their significance in algorithm analysis.
  • Explore common typographical errors in mathematical expressions and how to avoid them.
  • Learn about absolute values in the context of Big-O notation and their impact on function comparisons.
USEFUL FOR

Students studying computer science, algorithm analysts, and educators teaching algorithm complexity concepts.

s3a
Messages
828
Reaction score
8

Homework Statement


The problem and its solution is attached.


Homework Equations


Big-O notation.



The Attempt at a Solution


I get how to do this problem. The reason I'm making this post is for little details about the constants c and n_0. To my knowledge both c and n_0 have to be greater than 0. For n_0, if you use the definition of natural numbers which excludes 0 then I have no problem. On the other hand, the constant c being any real implies that it can be 0 or a negative number as well which doesn't fit in well with what I have learned.

Am I wrong or is the solution wrong? What are the subtleties here?
 

Attachments

  • Problem.jpg
    Problem.jpg
    21.4 KB · Views: 487
Physics news on Phys.org
O() is used for comparing the computations involved in computer algorithms, where c and no both need to be >0 for it to make sense. Beyond this, I can't say any more.

Seems to be a typo, that cn1.5 should be cn2.5 surely?
 
Yes, that n^(1.5) is a typo but it's not what I'm concerned about. ;)

Ok so, it seems that I must generally either make c > 0 or just let it be any constant including zero (it would technically work for a function that equals 0 and is big O of some other function where c = 0) or take the absolute value of the first function as well as the constant times the second function (which could be any real).

This problem puts no absolute value nor does it restrict c > 0 so having said that, the problem is incomplete, right?
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
Replies
2
Views
3K
  • · Replies 28 ·
Replies
28
Views
4K
  • · Replies 1 ·
Replies
1
Views
1K