Math Is Fun Forum

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

You are not logged in.

#2 Coder's Corner » Big O Notation calculation. » 2017-03-21 17:58:03

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. (:

#3 Re: Coder's Corner » Reducing the Expression of Time Complexity!!! » 2014-11-19 01:13:42

Ohhh!! yes!!! I got it...Hurray big_smile big_smile big_smile
Thank You very much Bob.

#4 Coder's Corner » Reducing the Expression of Time Complexity!!! » 2014-11-18 20:52:58

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??? hmm
05:   4T(n-4)+3c
06:   2{4T(n-4)+3c}+c  <-- HOW??? and HOW "...3c}+c"??? hmm
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?

#5 Coder's Corner » Help!!! Master Theorem? » 2013-01-08 23:09:06

azair
Replies: 3

Hello everyone wave, 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???dizzy]

{I'm assuming this tutorial's topic as : MASTER THEOREM FOR DUMMIES. big_smile}
Thanking you in advance...

Board footer

Powered by FluxBB