Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

hi JEF

no no.it's something we've done last year.

hi bobbym

well it would be nice.

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

HI;

Prove that n^3+20n -10 is not O(n^2).

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

hi

so n^3+20n-10>c*n^2 for any finite real number c>0.so n^3+20n-10 is w(n^2) and W(n^2) if i'm not mistaken.

i think that's enough for today.just tell me if i got this one right.

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

I do not remember about little w and Big W. But you are correct in the question.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

hi bobbym

next?

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Describe the growth of

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Hi anonimnystefy;

You have two questions for you to work on.

What does O(1) really mean? Put your answer in terms of a physical problem, something computer related.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

hi bobbym

1.n/((n+1)/2) is O(1)

2.O(1) means that an application with this complexity means that for any input it will take the same time to execute.e.g. the finding of the first element in an array has complexity of (1).

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Correct!

What is the Big(O) of this loop structure;

int x

for(x = 1; x<n; x*=2)

{

cout<< "hello";

}

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Hi anonimnystefy;

What does O(2^n) mean in cumputerese? Would you recommend an algorithm that had this amount of complexity?

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

hi bobbym

1.it's O(log n)

2.well it's time doubles when we add one more element.time grow very very quickly,so i would never recommend it.

unfortunately i cannot think of any algorithms that are O(2^n)

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Hi;

Very good!

You probably have never seen an O(2^n) algorithm.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

probably.you?

next?

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

When we say O(log(n)), clarify.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

it means that the algorithm execution time grow slower than a linear algorithm.for example if we have 1 element the execution time will be 1,if we have 2 then it's 2,but for 3 it's also 2,for 4 it would be 3,and so on.

example algorithm is binary search algorithm.

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

True but there is one more oddity about it. Check the notation for a clue.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

well i don't know what it is.maybe it's that the base needn't be specified.

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Hmmm! You were close. In normal mathematics log(n) means logs to the base e. Here it is in base 2.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**TheDude****Member**- Registered: 2007-10-23
- Posts: 361

Sorry to be pedantic, but when base isn't specified isn't log(n) usually base 10 and ln(n) base e?

Wrap it in bacon

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

hi bobbym

i don't agree.somewhere log is used to represent base 10 and ln for base e.

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Hi TheDude and anonimnystefy;

Yes, you are correct. I use ln rather than log, but Mathematica, (Wolfram ) uses the notation log(n) for the natural logarithm. I should have been clearer in making that distinction.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

it's okay.you're just used to it.

next?

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

Hold on, because I have answered this question before. If you look here

http://en.wikipedia.org/wiki/Logarithm

in notations near the top you will see that when no base is specified log(x) means the natural log ( base e ) and not the common one at least one branch of math too.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,522

the writer uses it like that as well and probably doesn't know about the other notation.

Here lies the reader who will never open this book. He is forever dead.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,569

It appears that either way depending on writers and branches of math both are correct.

For the purposes of asymptotic analysis log(n) means to the base 2.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**