Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Today in RAGE: Blog Driven Design

Name: Anonymous 2009-04-19 15:18

http://james.newtonking.com/archive/2009/04/18/blog-driven-design.aspx

Name: Anonymous 2009-04-19 15:21

You've been trolled (a good thing) - Trackback from dis.4chan.org

Name: Anonymous 2009-04-19 15:24

Trolling, the troll is banned! Less in parrot-fashion, less a rut, and their repetition also banned!
Troll, troll, please ignore. Please do not less sage.

Name: Anonymous 2010-11-26 14:22

Name: Anonymous 2011-02-18 20:32

Name: Anonymous 2012-09-25 21:41


   /  (n-1)        \
  |      ____          |
  |   \             |
  |      /___   2(x-1) | + 1     = total number of calls for Input N
   \    1          /

Name: Anonymous 2012-09-25 21:42


   /  (n-1)        \
  /   ____          |
  |   \             |
  |   /___   2(x-1) | + 1     = total number of calls for Input N
   \    1          /

Name: Anonymous 2012-09-25 21:43


   /  (n-1)        \
  /   ____          |
  |   \             |
  |   /___   2(x-1)   | + 1     = total number of calls for Input N
   \    1          /

Name: Anonymous 2012-09-25 21:43


   /  (n-1)        \
  /   ____          |
  |   \             |
  |   /___   2(x-1)  | + 1     = total number of calls for Input N
   \    1          /

Name: Anonymous 2012-09-25 21:43


   /  (n-1)        \
  /   ____          |
  |   \             |
  |   /___   2(x-1)  / + 1     = total number of calls for Input N
   \    1          /

Name: Anonymous 2012-09-25 21:43


   /  (n-1)        \
  |   ____          |
  |   \             |
  |   /___   2(x-1)  / + 1     = total number of calls for Input N
   \    1          /

Name: Anonymous 2012-09-25 21:44

>>39

T(1) = 1
T(N) = T(N-1)+T(N-2)+T(N-3)+...+T(1)+1
when you try simple substitution you should realize a pattern that only the functions to the left can spawn (1) function seen to the right. i.e: T(N) can only spawn 1 T(N-1) call; therefore, we can start to notice that the coefficients of each call T(M) for some M < N should be 2(N-M-1). i.e: N = 5, M = 4 T(4) coefficient should be 25-4-1 = 1


T(N) = (2(1-1))T(N-1) + (2(2-1))T(N-2) + ... + (2((N-1)-1)T(1) + 1
simplifing T(1) coefficient
T(N) = (2(1-1))T(N-1) + (2(2-1))T(N-2) + ... + (2(N-2)T(1) + 1
T(N) = (1)T(N-1) + (2)T(N-2) + ... + (2(N-2))T(1) + 1
Since the coefficient equates to the number of times we'll call T with argument M for some integer we can see that this is a simple series:
   
   /  (n-1)        \
  |   ____          |
  |   \             |
  |   /___   2(x-1)  / + 1     = total number of calls for Input N
   \    1          /

Using some math, you should be able to reason the series to become simply:
  (2(n-1)-1)+1
=> 2(n-1)

Therefore: O(2(n-1))


is that a good enough proof?

Name: Anonymous 2013-01-18 23:20

/prog/ will be spammed continuously until further notice. we apologize for any inconvenience this may cause.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -