Effiecient programming

[myst]

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.

[JosAH]

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

[myst]

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

[JosAH]

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

[bleah]

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.

[JosAH]

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

[myst]

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.....

[JosAH]

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

[myst]

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...

[JosAH]

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

[myst]

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??

[JosAH]

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:

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

[myst]

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.

[myst]

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)

[xcallmejudasx]

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.