Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
#54 (Reducing Recurrence)
#1
Quote:54. The recurrence: T(n) = T(n-1) + O(1) reduces to:
  1. O((log n)*(log n))
  2. O(n)
  3. O(log n)
  4. O(n log n)
This doesn't fit the form of the MRT, right? I'm pretty sure the answer is O(n) despite that. How should I approach reducing this though?
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
Reply
#2
Common sense. Or you can write out the open form and use math to find the closed form.
Reply
#3
Seems to be O(n). Each time you recurse you get 1 sub-problem of size (n - 1) where you perform constant work for every sub-problem. Looks like you get the equation: n sub-problems * constant work = O(n)
Reply
#4
^ very good
Reply
#5
Can you explain how to solve this with substitution?

Tried my hand at it, but don't think I'm going about this the right way:

T(n) = T(n-1) + O(1)
T(log n) = T(log(n) - log(2)) + O(1)
T(log n) = T(log(n/2)) + O(1)

let S(m) = T(log n) = S(m/2) + O(1)
...
???????????


log base 2 of 1 = 0...? But this can't be case 2 - then I'd get theta(m log m) = theta(2^n * n). Help!
Reply
#6
(09-14-2017, 06:14 PM)SSinischo Wrote: Can you explain how to solve this with substitution?

Tried my hand at it, but don't think I'm going about this the right way:

T(n) = T(n-1) + O(1)
T(log n) = T(log(n) - log(2)) + O(1)
T(log n) = T(log(n/2)) + O(1)

let S(m) = T(log n) = S(m/2) + O(1)
...
???????????


log base 2 of 1 = 0...?  But this can't be case 2 - then I'd get theta(m log m) = theta(2^n * n).  Help!

You should be careful with making a substitution with the same variable name.

T(n) = T(n-1) + O(1)
Let n = lg(m)
T(lg(m)) = T(lg(m) - lg(2)) + O(1) = T(lg(m/2)) + O(1)
Let S(m) = T(lg(m))
S(m) = S(m/2) + O(1)
m^log_b(a) = m^log_2(1) = m^0 = Θ(1) -> Case 2 -> S(m) = Θ(m^0 * lg(m)) = Θ(lg(m)) = T(n) = Θ(n)

Also note that, although it didn't matter in this particular example, the constant hidden in O(f(n)) can sometimes matter because across substitutions the constant can become an exponent.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)