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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

thanks (:

**azair**- Replies: 3

Help me!

Given an equation f(n) = 3n²-100n+6

How can you prove that f(n) = O(n²). Definition for O → |f(n)| <= c* |g(n)|.

My professor has taken c=3 and nₒ=34. So if n > nₒ = 34 → we can get rid of the absolute values. → |f(n)|=f(n). ... ... ...

>>>My question is, how did he get the c as 3 and nₒ as 34? Is it taken randomly??? or is it this way???:

3n²-100n = 0 (ignoring 6[c as standalone constant])

3n² = 100n

n = 100/3 = 33.333333 ≈ 34.

Is this correct??? Please advice.

=>Also proving f(n) = O(n³) , we are taking c = 1 and nₒ = 34. Why is c=1 here??

Thanks in advance and regards. (:

Ohhh!! yes!!! I got it...Hurray

Thank You very much Bob.

**azair**- Replies: 2

Hello Everyone,

I was trying to understand the calculation regarding the Time-Complexity of an Algorithm, but got stuck @line no :04 and 06

Here is the problem :

01: T(n)=T(n-1)+T(n-2)+4 and T(0)=T(1)=1

02: Lets assume that T(n-1)~T(n-2)

03: then, T(n)=2T(n-2)+c where c=4

04: 2{2T(n-4)+c}+c <-- HOW???

05: 4T(n-4)+3c

06: 2{4T(n-4)+3c}+c <-- HOW??? and HOW "...3c}+c"???

07: 16T(n-8)+15c

and therefore,

08: T(n)=2^k T(n-2k)+(2^k -1)c

09: T(n)=2^n/2 T(0) + (2^n/2 -1)c since: n-2k=0; k=n/2.

10: T(n)=(1+c)2^k - c.

=>I just don't understand as to what is happening @line 04 and 06.

Can anyone help me?

**azair**- Replies: 3

Hello everyone , I am learning an Algorithm analysis on my own and today I came across 'Master Theorem for Divide and Conquer'. Since I'm quite not good at Mathematics, this topic is giving me a full headache.(ahem ahem, no offense please!!! ;-)).

Alright, The definition is given as follows :

"If the recurrence is of the form T(n)=aT(n/b)+Θ(n^k log^p n),where a>=1, b>1, k>=0 and p is a real number, then:

1.) If a>b^k, then T(n)=Θ(n^log^a↓b) [Note : lets assume ↓ as base.]2.) If a=b^k :

a.) If p>-1, then T(n)=Θ(n^log^a↓b * log^p+1 n)

b.) If p=-1, then T(n)=Θ(n^log^a↓b * loglog n)

c.) If p<-1, then T(n)=Θ(n^log^a↓b).3.) If a<b^k :

a.) If p>=0, then T(n)=Θ(n^k log^p n)

b.) If p<0, then T(n)=O(n^k).

"

Well can anyone help me explain what these means in simple terms with an example if possible.

For example : Problem--> T(n)=2T(n/2)+nlogn. [The Answer is Θ(nlog logn) :? How???]

{I'm assuming this tutorial's topic as : MASTER THEOREM FOR DUMMIES. }

Thanking you in advance...

Pages: **1**