<![CDATA[CodeGuru Forums - Algorithms & Data Structures]]>
http://forums.codeguru.com/
enSun, 26 Mar 2017 14:38:11 GMTvBulletin60http://forums.codeguru.com/images/misc/rss.png<![CDATA[CodeGuru Forums - Algorithms & Data Structures]]>
http://forums.codeguru.com/
recursion tree method to solve the recurrence
http://forums.codeguru.com/showthread.php?558807-recursion-tree-method-to-solve-the-recurrence&goto=newpost
Sun, 12 Mar 2017 17:16:16 GMT n - 1 and n/2
left branch: n-1 -> n-2 and (n-1)/2
right branch: n/2-1 and n/4
etc.
the tree isn't a complete binary tree, but we know that the longest path from root to leaf is the one from n -> n-1 -> n-2 -> ... -> 1 which is n levels. so the height if the tree is n.
calculating the costs at each level:
level 0: n
level 1: n-1 + n/2 = 3/2n - 1
level 2: (9n-12)/4 = (3/2)^2 - 3
here we see a pattern: the cost of each level is (3/2)^i - b, for levels i = 0,1,2,...,n-1
=> T(n) = sum(i=0,n-1) (3/2)^i * n = n * [ (3/2)^n - 1 / (3/2) - 1 ] = 2n *[ (3/2)^n - 1 ] = 2n * (3/2)^n - 2n = O(n*(3/2)^n)?
i'm not sure that this is correct. is it? i've viewed a few other solutions on the internet but none of them even looks like this, one says it's O(n^2), the other - O(2^theta(logn)).
thanks in advance]]>i'm solving exercises from cormen's algorithms (3rd edition) using recursion tree but i'm stuck with this one: T(n) = T(n-1) + T(n/2) + n.

as usual, i first draw the tree (i drew the tree here but the formatting didn't show correctly so this is the "tree", ugh):

root: n -> n - 1 and n/2
left branch: n-1 -> n-2 and (n-1)/2
right branch: n/2-1 and n/4
etc.

the tree isn't a complete binary tree, but we know that the longest path from root to leaf is the one from n -> n-1 -> n-2 -> ... -> 1 which is n levels. so the height if the tree is n.

calculating the costs at each level:
level 0: n
level 1: n-1 + n/2 = 3/2n - 1
level 2: (9n-12)/4 = (3/2)^2 - 3

here we see a pattern: the cost of each level is (3/2)^i - b, for levels i = 0,1,2,...,n-1
=> T(n) = sum(i=0,n-1) (3/2)^i * n = n * [ (3/2)^n - 1 / (3/2) - 1 ] = 2n *[ (3/2)^n - 1 ] = 2n * (3/2)^n - 2n = O(n*(3/2)^n)?

i'm not sure that this is correct. is it? i've viewed a few other solutions on the internet but none of them even looks like this, one says it's O(n^2), the other - O(2^theta(logn)).

thanks in advance
]]>user4592357http://forums.codeguru.com/showthread.php?558807-recursion-tree-method-to-solve-the-recurrencemaster method explanation
http://forums.codeguru.com/showthread.php?558771-master-method-explanation&goto=newpost
Wed, 08 Mar 2017 18:05:21 GMThere are presented the 3 cases of using master method http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
can someone explain why we multiply the solution by logn when f(n) = theta(n^logb_a) (second case in pdf)? thanks in advancehere are presented the 3 cases of using master method http://www.csd.uwo.ca/~moreno/CS433-...ces/master.pdf

can someone explain why we multiply the solution by logn when f(n) = theta(n^logb_a) (second case in pdf)? thanks in advance
]]>user4592357http://forums.codeguru.com/showthread.php?558771-master-method-explanation<![CDATA[express function in Ω-notation]]>
http://forums.codeguru.com/showthread.php?558737-express-function-in-Ω-notation&goto=newpost
Sun, 05 Mar 2017 20:10:04 GMTi'm learning algorithm analysis, about the different notations, and in class we wrote an example:

f(n) = 1/2*n^2 + 3n,

and wrote it using O-notation, Ω-notation and Θ-notation:

T(n) = Ω(n)
T(n) = O(n^2)
T(n) = Θ(n^2)

now i'm reading the book, where it says f(n) = Θ(g(n)) is true if and only if both f(n) = O(g(n)) and f(n) = Ω(g(n)) are correct.

in the example we wrote, it says T(n) = Θ(n^2) (which i do agree with) which means both T(n) = O(n^2) and T(n) = Ω(n^2) should hold. but we wrote T(n) = Ω(n). i think that's incorrect? (we wrote that because of the term 3n which means that at least 3n operations are done)

i think it should be T(n) = Ω(n^2) instead of Ω(n)

please correct me if i'm wrong. thanks in advance
]]>user4592357