-3

I'm trying to see if I'm correct in my work for finding the big-O notation of some formulas. Each of these formulas are the number of operations in some algorithm. These are the formulas:

Forumulas

a.) n2 + 5n

b.) 3n2 + 5n

c.) (n + 7)(n - 2)

d.) 100n + 5

e.) 5n +3n2

f.) The number of digits in 2n

g.)The number of times that n can be divided by 10 before dropping below 1.0

My answers:

a.) O(n2)

b.) O(n2)

c.) O(n2)

d.) O(n)

e.) O(n2)

f.) O(n)

g.) O(n)

Am I correct on my analysis?

1 Answer 1

3

Let's go through this one at a time.

a.) n2 + 5. Your answer: O(n2)

Yep! You're ignoring lower-order terms correctly.

b.) 3n2 + 5n. Your answer: O(n2).

Yep! Big-O eats constant factors for lunch.

c.) (n + 7)(n - 2). Your answer: O(n2).

Yep! You could expand this out into n2 + 5n - 14 and from there drop the low-order terms to get O(n2), or you could realize that n + 7 = O(n) and n - 2 = O(n) to see that this is the product of two terms that are each O(n).

d.) 100n + 5. Your answer: O(n).

Yep! Again, dropping constants and lower-order terms.

e.) 5n + 3n2. Your answer: O(n2).

Yep! Order is irrelevant; 5n is still a low-order term.

f.) The number of digits in 2n. Your answer: O(n).

This one is technically correct but is not a good bound. Remember that big-O notation gives an upper bound and you are correct that the number n has O(n) digits, but only in the sense that the number of digits of n is asymptotically less than n. To see why this bound isn't very good, let's look at the numbers 10, 100, 1000, 10000, and 100000. These numbers have 2, 3, 4, 5, and 6 digits, respectively. In other words, growing by a factor of ten only grows the number of digits by one. If the O(n) bound you had were tight, then you'd expect that the number of digits would grow by a factor of ten every time you made the number ten times bigger, which isn't accurate.

As a hint for this one, if a number has d digits, then it's between 10d and 10d+1 - 1. That means the numeric value of a d-digit number is exponential as a function of d. So, if you start with a number of digits, the numeric value is exponentially larger. Try running this backwards. If you have a numeric value that you know is exponentially larger than the number of digits, what does that mean about the number of digits as a function of the numeric value?

f.) The number of times that n can be divided by 10 before dropping below 1.0. Your answer: O(n)

This one is also technically correct but not a very good bound. Let's take the number 100,000, for example. You can divide this by 10 seven times before you drop below 1.0, but giving a bound of O(n) means that you're saying the answers grows linearly as a function of n, so doubling n should double the number of times you can divide by ten... but is that actually the case?

As a hint, the number of times you can divide a number by ten before it drops below 1.0 is closely related to the number of digits in that number. If you can figure out this problem, you'll figure out part (e), and vice-versa.

Good luck!

2
  • "You can divide this by 10 seven times before you drop below 1.0, but giving a bound of O(n) means that you're saying the answer would be at most 100,000. " As you mention yourself, there can always be a constant in front of the term inside the O, so O(n) does not mean that 100000 will take 100000 of anything. Similarly for e). Better is something like: "O(n) means, that '100' will have at most 10 times as many digits as '10' does and '1000' at most 100 times as many. Obviously this is not very tight."
    – example
    Aug 26, 2016 at 22:43
  • @example You're absolutely right. Let me fix that. Aug 26, 2016 at 23:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.