Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

i know its sounds like a very general question. but actually i learn this week a lot on the matter and i understand it very good.

my more specific question is , from your experiance, there's a "trick" , maybe some better way to figure out quickly for example how to make an algorithm of time complexity O(N^2)

to O(N) .

i succeed doing so in self study yestarday, when i had in a code two nested for loops and i rewrote it as a while loop. so i changed time complexity from O(N^2) to O(N).

but as the algorithm is more complicated, such will be the assigment to improve time and place complexity.

for example i have this code :

so i have 3 questions / shares :

1. do you have a way, or certain behavior that helps you to make an algorithm more efficient ? (in general)

2 .i think that time complexity here is O(N^2) , but what is the space complexity ? i think its O(1) there's no allocating for a large input , it just constant allocate for variable temp value, am i right or wrong ?

3. i thought about ways to make this algroithm more efficient . maybe (N log N , or N). i think N is makeing more sense , am I in the right direction ?

i will continue on this tomorrow, i learn a lot today. and need some sleep, so for question 3 just tell me if i'm in the right direction. i will try to solve it tomorrow.

for questions 1 and 2 i will be glad for some answers.

thanks

my more specific question is , from your experiance, there's a "trick" , maybe some better way to figure out quickly for example how to make an algorithm of time complexity O(N^2)

to O(N) .

i succeed doing so in self study yestarday, when i had in a code two nested for loops and i rewrote it as a while loop. so i changed time complexity from O(N^2) to O(N).

but as the algorithm is more complicated, such will be the assigment to improve time and place complexity.

for example i have this code :

so i have 3 questions / shares :

1. do you have a way, or certain behavior that helps you to make an algorithm more efficient ? (in general)

2 .i think that time complexity here is O(N^2) , but what is the space complexity ? i think its O(1) there's no allocating for a large input , it just constant allocate for variable temp value, am i right or wrong ?

3. i thought about ways to make this algroithm more efficient . maybe (N log N , or N). i think N is makeing more sense , am I in the right direction ?

i will continue on this tomorrow, i learn a lot today. and need some sleep, so for question 3 just tell me if i'm in the right direction. i will try to solve it tomorrow.

for questions 1 and 2 i will be glad for some answers.

thanks

posted 2 years ago

Yes, your answers to #2 are correct.

As for #3: you could possibly replace lines 19 and 20 by a call to the System.arrayCopy method with suitable parameters. That might speed the algorithm up, but we (or at least I) have no idea whether that method uses an O(1) or an O(N) algorithm to copy N array entries. My guess would be the latter but I could be wrong. Or partially wrong. So that just obscures the issue.

Also as for #3: there is a way to modify that algorithm to make it an O(N) algorithm. However that way is to throw it away completely and replace it by a different algorithm which is O(N). Such an algorithm does exist but I leave it as an exercise for the student to find it.

As for #1: There's no general algorithm for converting an O(N^2) algorithm into an O(N) algorithm. As I implied earlier, the usual way to do that is to replace the O(N^2) algorithm by a completely different O(N) algorithm, although it might be possible to do the conversion if the original algorithm was very badly written.

As for #3: you could possibly replace lines 19 and 20 by a call to the System.arrayCopy method with suitable parameters. That might speed the algorithm up, but we (or at least I) have no idea whether that method uses an O(1) or an O(N) algorithm to copy N array entries. My guess would be the latter but I could be wrong. Or partially wrong. So that just obscures the issue.

Also as for #3: there is a way to modify that algorithm to make it an O(N) algorithm. However that way is to throw it away completely and replace it by a different algorithm which is O(N). Such an algorithm does exist but I leave it as an exercise for the student to find it.

As for #1: There's no general algorithm for converting an O(N^2) algorithm into an O(N) algorithm. As I implied earlier, the usual way to do that is to replace the O(N^2) algorithm by a completely different O(N) algorithm, although it might be possible to do the conversion if the original algorithm was very badly written.

Dan D'amico

Ranch Hand

Posts: 94

posted 2 years ago

yes. i understand.

i also thought maybe to rewrite the code such that it will be O(n log n).

rewrite it like merge sort, such that the sort will be defined by even numbers to the left and even numbers to the right.

yes, if it needed to throw it completely, it will be possible.

Paul Clapham wrote:

As for #1: There's no general algorithm for converting an O(N^2) algorithm into an O(N) algorithm. As I implied earlier, the usual way to do that is to replace the O(N^2) algorithm by a completely different O(N) algorithm, although it might be possible to do the conversion if the original algorithm was very badly written.

yes. i understand.

i also thought maybe to rewrite the code such that it will be O(n log n).

rewrite it like merge sort, such that the sort will be defined by even numbers to the left and even numbers to the right.

Paul Clapham wrote:

Also as for #3: there is a way to modify that algorithm to make it an O(N) algorithm. However that way is to throw it away completely and replace it by a different algorithm which is O(N). Such an algorithm does exist but I leave it as an exercise for the student to find it.

yes, if it needed to throw it completely, it will be possible.