Posts by azair

azair · Coder's Corner

thanks (:

azair · Coder's Corner

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

azair · Coder's Corner

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

azair · Coder's Corner

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 · Coder's Corner

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

Math Is Fun Forum

#1 Re: Coder's Corner » Big O Notation calculation. » 2017-04-15 05:37:57

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

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

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

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

Board footer