Results 1 to 15 of 15
Thread: Effiecient programming
 05302010, 01:13 PM #1Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
Effiecient programming
We were given a program and asked to determine the runtime.
I discovered the pattern looks like this: n+(n1)+(n3)+(n5)+...+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; 05302010 at 01:17 PM.
 05302010, 01:43 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
 05302010, 02:24 PM #3Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
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=7; 7+6+4+2+1
Not sure if there is a difference between the two:
Even: n+(n1)+(n3)+...+3+1
Odd: n+(n1)+(n3)+...+2+1
 05302010, 03:30 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
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
 05302010, 04:13 PM #5
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.
 05302010, 04:33 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
 05312010, 06:21 AM #7Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
This is a O(1) problem; bigoh hasn't much to do with it; it's just a bit of math.
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.....
 05312010, 07:35 AM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
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
 05312010, 10:26 AM #9Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
I didn't want to post the code but...
*Remember, we have to determine what the program does and runtime of this program. And then rewrite the program, making it more efficient. If the runtime 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;
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 ;)Last edited by myst; 05312010 at 01:07 PM.
 05312010, 10:54 AM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
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
 05312010, 11:29 AM #11Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
I can't answer changing problems with changing requirements
Do you at least understand what I was getting at before??
 05312010, 11:37 AM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,519
 Blog Entries
 7
 Rep Power
 20
No, this is your original post:
Originally Posted by you
kind regards,
JosLast edited by JosAH; 05312010 at 11:53 AM.
 05312010, 12:58 PM #13Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
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.
O(n+(n1)+(n3)+(n5)+...+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.
 05312010, 01:07 PM #14Member
 Join Date
 May 2010
 Posts
 44
 Rep Power
 0
In my original post I wrote:
I discovered the pattern looks like this: n+(n1)+(n3)+(n5)+...+1.
 06012010, 05:27 PM #15
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

new to programming need help with something
By surg3y3 in forum New To JavaReplies: 4Last Post: 01262010, 03:13 AM 
GUI Programming Help
By sirwiggles in forum New To JavaReplies: 4Last Post: 04282009, 04:53 AM 
New to Programming . . .Need Help
By DSutta22 in forum New To JavaReplies: 2Last Post: 09102008, 05:19 AM 
HELP, just started programming
By TankMurdoch in forum New To JavaReplies: 3Last Post: 08072008, 01:41 PM 
programming
By abcdefg in forum New To JavaReplies: 9Last Post: 03102008, 10:34 AM
Bookmarks