Results 1 to 15 of 15
  1. #1
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default Effiecient programming

    We were given a program and asked to determine the run-time.

    I discovered the pattern looks like this: n+(n-1)+(n-3)+(n-5)+...+1.

    My only issue is that I forgot how to make this into a formula. Can somebody help with this and also send me a link where they explain this type of work. I forget what this type of math is called so I don't know where to search. Thanks.
    Last edited by myst; 05-30-2010 at 01:17 PM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,458
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by myst View Post
    We were given a program and asked to determine the run-time.

    I discovered the pattern looks like this: n+(n-1)+(n-3)+(n-5)+...+1.

    My only issue is that I forgot how to make this into a formula. Can somebody help with this and also send me a link where they explain this type of work. I forget what this type of math is called so I don't know where to search. Thanks.
    Be careful here; what if n == 6? is it 6+5+3+1; then what if n == 7? is it 7+6+4+2+0?

    kind regards,

    Jos
    Last edited by JosAH; 05-30-2010 at 02:06 PM.

  3. #3
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    Be careful here; what if n == 6? is it 6+5+3+1; then what if n == 7? is it 7+6+4+2+0?
    n=6; 6+5+3+1

    n=7; 7+6+4+2+1

    Not sure if there is a difference between the two:

    Even: n+(n-1)+(n-3)+...+3+1
    Odd: n+(n-1)+(n-3)+...+2+1

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,458
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by myst View Post
    n=6; 6+5+3+1

    n=7; 7+6+4+2+1

    Not sure if there is a difference between the two:

    Even: n+(n-1)+(n-3)+...+3+1
    Odd: n+(n-1)+(n-3)+...+2+1
    Ok, as we all know (or should know) the sum of the numbers 1+2+3+4 ... +n == n*(n+1)/2.
    so twice that number is the sum of all even numbers <= 2*n: n*(n+1); Correcting for an even n value: (n/2)*(n/2+1)

    So we have:

    for any n >= 0: n*(n+1)/2
    for any even n >= 0: (n/2)*(n/2+1)

    if we subtract one from each term we are adding all odd numbers:

    for any odd n >= 0: ((n+1)/2)*((n+1)/2+1)-(n+1)/2 == ((n+1)/2)^2

    (as a corollary: the sum of the first n odd numbers is a square).

    You should be able to juggle a bit further to be able to get a closed form expression for your sequence of numbers.

    kind regards,

    Jos

  5. #5
    bleah's Avatar
    bleah is offline Member
    Join Date
    May 2010
    Posts
    13
    Rep Power
    0

    Default

    The thing is called Big O notation. But still I don't know how to calculate. Looks complex. Google for Big O and you will probably find some help.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,458
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by bleah View Post
    The thing is called Big O notation. But still I don't know how to calculate. Looks complex. Google for Big O and you will probably find some help.
    This is a O(1) problem; big-oh hasn't much to do with it; it's just a bit of math.

    kind regards,

    Jos

  7. #7
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    This is a O(1) problem; big-oh hasn't much to do with it; it's just a bit of math.
    How can this be O(1)? This is at least O(n): The program must check from the first char - n char. Then it checks from second char - n char,..., up until n char.

    for n=7: 7+6+4+2+1 = 7 + 6(6+2)/4 +1 --- n+1+n(n+2)/4

    for n=6: 6+5+3+1 = 6+((5+1)^2)/4 --- n+((n+1)^2)/4

    Is there a way I can combine both those formulas into a general one or will I need two base statements in recursion (for even and odd):

    if (n%2 ==0)
    if (n==2)
    return.....

    if (n%2 !=0)
    if (n==1)
    return.....

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,458
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by myst View Post
    How can this be O(1)? This is at least O(n): The program must check from the first char - n char. Then it checks from second char - n char,..., up until n char.

    for n=7: 7+6+4+2+1 = 7 + 6(6+2)/4 +1 --- n+1+n(n+2)/4

    for n=6: 6+5+3+1 = 6+((5+1)^2)/4 --- n+((n+1)^2)/4

    Is there a way I can combine both those formulas into a general one or will I need two base statements in recursion (for even and odd):
    It is an O(1) algorithm because it can find the answer in one single step: it has to find the right formula (according whether or not n is even) and calculate its value. There's nothing in there proportional to n or n^2 or log(n) or whatvever; there's also no recursion involved. Just two formulas: if n is even, it's the value of the first formula, otherwise it's the second formula.

    Not the entire world is loops or recursion ;-)

    kind regards,

    Jos

  9. #9
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    I didn't want to post the code but...
    *Remember, we have to determine what the program does and run-time of this program. And then rewrite the program, making it more efficient. If the run-time is O(1), there's no point of rewriting it...it's as efficient as it gets.

    * code removed

    if you type what("mississippi", 'i', 's'), count will equal 6. It counts the amount of 's' after the first 'i', the amount of 's' after the second 'i'... 4+2=6.

    I believe the worst case scenario is when you type what("aoao...",'a', 'o') at length n. It checks the amount of 'o' after every 'a', and there's n/2 'a' in the string. That's a lot of checking...

    Then I got to the formula:

    Even -- n+((n+1)^2)/4
    Odd -- n+1+n(n+2)/4


    It is an O(1) algorithm because it can find the answer in one single step: it has to find the right formula (according whether or not n is even) and calculate its value. There's nothing in there proportional to n or n^2 or log(n) or whatvever;
    They say, generally when you have a double "for" loop, the worst case run-time is O(n^2).

    there's also no recursion involved. Just two formulas: if n is even, it's the value of the first formula, otherwise it's the second formula.

    Not the entire world is loops or recursion ;-)
    I just assumed using recursion may help make it a better run-time. I could always try using different type of if/for loops...
    Last edited by myst; 05-31-2010 at 01:07 PM.

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,458
    Blog Entries
    7
    Rep Power
    20

    Default

    You are solving an entirely different problem there. I can't answer changing problems with changing requirements. I'm out of this thread.

    kind regards,

    Jos

  11. #11
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    I can't answer changing problems with changing requirements
    What do you mean by changing problems by changing requirements?

    Do you at least understand what I was getting at before??

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,458
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by myst View Post
    What do you mean by changing problems by changing requirements?

    Do you at least understand what I was getting at before??
    No, this is your original post:

    Quote Originally Posted by you
    We were given a program and asked to determine the run-time.

    I discovered the pattern looks like this: n+(n-1)+(n-3)+(n-5)+...+1.

    My only issue is that I forgot how to make this into a formula. Can somebody help with this and also send me a link where they explain this type of work. I forget what this type of math is called so I don't know where to search.
    There is no 'mississipii', nor characters, nor arbitrary Strings in there. You simply were looking for a closed form of a sequence. You at least should be clear from the start and don't change your problem and your requirements on the fly; good luck with it.

    kind regards,

    Jos
    Last edited by JosAH; 05-31-2010 at 11:53 AM.

  13. #13
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    There is no 'mississipii', nor characters, nor arbitrary Strings in there. You simply were looking for a closed form of a sequence. You at least should be clear from the start and don't change your problem and your requirements on the fly; good luck with it.
    Sorry, all I was trying to say is that the worst case run-time is n+(n-1)+(n-3)+(n-5)+...+1.

    O(n+(n-1)+(n-3)+(n-5)+...+1) and all I was asking is how to make this into a formula.

    And because of your assistance I got

    O (n+((n+1)^2)/4)

    which would simply make it

    O(n^2)

    Thanks.

  14. #14
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default

    In my original post I wrote:
    I discovered the pattern looks like this: n+(n-1)+(n-3)+(n-5)+...+1.
    I guess I meant to write, I discovered the worst case scenario is...which is why it can't be O(1), it must be at least O(n)

  15. #15
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    Correct. Run time is used to determine how many times a point in a function will run(hence the name). Say for example you have print(1+1), that will have a constant time O(1) because there's no loops or functions calls.

    Now
    for(int i = 0; i < 10; i++)
    print("hello");

    will have a run time O(n), where n is the number of loops, because it's a single loop.

    Something like
    while(x < 10){
    for(int i = 0; i <= 10; i++){
    x = i;
    }
    }

    will have a run time of O(n^2), this is because you have two equations. The inner and outer, both of them running n times so the runtime gets squared.

    Hope that helped clarify things.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

Similar Threads

  1. new to programming need help with something
    By surg3y3 in forum New To Java
    Replies: 4
    Last Post: 01-26-2010, 03:13 AM
  2. GUI Programming Help
    By sirwiggles in forum New To Java
    Replies: 4
    Last Post: 04-28-2009, 04:53 AM
  3. New to Programming . . .Need Help
    By DSutta22 in forum New To Java
    Replies: 2
    Last Post: 09-10-2008, 05:19 AM
  4. HELP, just started programming
    By TankMurdoch in forum New To Java
    Replies: 3
    Last Post: 08-07-2008, 01:41 PM
  5. programming
    By abcdefg in forum New To Java
    Replies: 9
    Last Post: 03-10-2008, 10:34 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •