 |  |  |  |  |  |  |  |
Time complexity help
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
Thread Solved |
Hey, I'm new to the site and also newbie in time complexity subject. I've read plenty of theoretical approaches and also some examples but I'm still having quite some troubles with determining time complexity of some of my algorhytms, especially recursion. It is quite a delicate thing so I would ask for your help if somebody can explain me through my algorhytms how to determine time complexity properly.
Here are my algorhytms:
Recursion1:
Iteration1:
Recursion2:
Iteration2:
I think this one is O(x^2 + x*y) if I understood the basics but I would rather see someone more experienced determine it properly.
Recursion3:
Iteration3:
Thank you for the help.
Here are my algorhytms:
Recursion1:
public static long rec(long n){
if(n == 0){
return 0;
}
else if(n == 1){
return 1;
}
else{
return 2*rec(n-1) + rec(n-2);
}
}Iteration1:
public static long iter(long n){
long a0 = 0, a1 = 1, tmp;
if(n == 0){
return 0;
}
else{
for(long i=n; i>1; i--){
tmp = a0;
a0 = a1;
a1 = 2*a0 + tmp;
}
return a1;
}
}Recursion2:
public static long factorial(long n){
if(n <= 1){
return 1;
}
else{
return n * factorial(n-1);
}
}
public static long dominoes(long x, long y){
return factorial(x+y) / (factorial(x)*factorial(y));
}Iteration2:
public static long dominoes(long x, long y){
long temp;
double koeficient = 0, faktor;
if(y > x){
temp = x;
x = y;
y = temp;
}
for(long i=0; i<=x+y; i++){
koeficient = 1;
for(int j=1; j<y+1; j++){
faktor = ((double)((i+1)-j)) / (double)j;
faktor = koeficient * faktor;
koeficient = faktor;
}
}
return (long)koeficient;
}Recursion3:
public static String reverse(String str){
if(str.length() <= 1 || str == null){
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}Iteration3:
public static String reverse(String str){
String str2 = "";
for(int i=str.length()-1; i>=0; i--){
str2 += str.charAt(i);
}
return str2;
}Thank you for the help.
0
#2 24 Days Ago
I also forgot to ask before... What is the time complexity of BigInteger (in Java)?
•
•
Join Date: Jun 2005
Posts: 2,047
Reputation: 
Solved Threads: 139
3
#3 24 Days Ago
•
•
•
•
Originally Posted by complexTime 
I also forgot to ask before... What is the time complexity of BigInteger (in Java)?
All my posts may be redistributed under the GNU Free Documentation License.
•
•
Join Date: Jun 2005
Posts: 2,047
Reputation:
Solved Threads: 139
7
#4 24 Days Ago
Let's look at this one. I'm going to ignore the swap for now.
Iteration2:
Let's add annotations, giving the cost of each line.
When we have successive statements with cost O(x) and O(y), their combined cost is O(x + y). Let's first remove the pieces of code that we've accounted for.
You'll note that the lines of code don't modify i or j. If there was some line that said "i = i * i", we wouldn't want to delete that because it would affect the number of iterations of the loop.
Now let's combine successive statements.
I've written O(2) and O(4) for didactic purposes -- really we'd just write O(1) since O(2) and O(1) are the same thing.
Now let's look at the inner loop. Its body takes O(1) time. It runs y iterations. So the running time is O(y)*O(1) = O(y).
Now O(1) + O(y) = O(y) so we can combine those successive costs.
Now the outer loop runs x+y times. The interior costs O(y) time. So the cost of the loop is O(x+y) * O(y) = O((x+y)*y).
And O(1) + O((x+y)*y) + O(1) = O((x+y)*y).
And we're done.
Ignoring the swap that we decided to ignore, the cost is O((x+y)*y). But the truth is that after the swap, if it happens or not, the variable x will contain the minimum of the x and y parameters, and y will contain the maximum. So, accounting for the swap, the running time is O((min(x,y) + max(x,y)) * max(x,y)).
Are we done? We could be. But it's useful to simplify our answer. Note that 1*max(x,y) <= (min(x,y) + max(x,y)) <= 2*max(x,y). Therefore, max(x,y)^2 <= (min(x,y)+max(x,y))*max(x,y) <= 2*max(x,y)^2.
So (min(x,y)+max(x,y))*max(x,y) is Theta(max(x,y)^2) (which is a way to say the two functions are O of one another). This means we can say our function is O(max(x,y)^2) without losing any information.
Like, we could say our function is O(max(x,y)^3), and we'd lose information -- because it's a weaker bound. The fact that (min(x,y) + max(x,y))*max(x,y) is Theta(max(x,y)) means that O(max(x,y)^2) is as strong a bound.
Iteration2:
public static long dominoes(long x, long y){
long temp;
double koeficient = 0, faktor;
for(long i=0; i<=x+y; i++){
koeficient = 1;
for(int j=1; j<y+1; j++){
faktor = ((double)((i+1)-j)) / (double)j;
faktor = koeficient * faktor;
koeficient = faktor;
}
}
return (long)koeficient;
} public static long dominoes(long x, long y){
long temp; // O(1)
double koeficient = 0, faktor; // O(1)
for(long i=0; i<=x+y; i++){
// an O(1) cost for (i <= x+y) and (i++)
koeficient = 1; // O(1)
for(int j=1; j<y+1; j++){
// an O(1) cost for (j < y+1) and (j++)
faktor = ((double)((i+1)-j)) / (double)j; // O(1)
faktor = koeficient * faktor; // O(1)
koeficient = faktor; // O(1)
}
}
return (long)koeficient; // O(1)
} public static long dominoes(long x, long y){
// O(1)
// O(1)
for(long i=0; i<=x+y; i++){
// O(1)
// O(1)
for(int j=1; j<y+1; j++){
// O(1)
// O(1)
// O(1)
// O(1)
}
}
return; // O(1)
}You'll note that the lines of code don't modify i or j. If there was some line that said "i = i * i", we wouldn't want to delete that because it would affect the number of iterations of the loop.
Now let's combine successive statements.
public static long dominoes(long x, long y){
// O(2)
for(long i=0; i<=x+y; i++){
// O(2)
for(int j=1; j<y+1; j++){
// O(4)
}
}
return; // O(1)
}I've written O(2) and O(4) for didactic purposes -- really we'd just write O(1) since O(2) and O(1) are the same thing.
public static long dominoes(long x, long y){
// O(1)
for(long i=0; i<=x+y; i++){
// O(1)
for(int j=1; j<y+1; j++){
// O(1)
}
}
return; // O(1)
}Now let's look at the inner loop. Its body takes O(1) time. It runs y iterations. So the running time is O(y)*O(1) = O(y).
public static long dominoes(long x, long y){
// O(1)
for(long i=0; i<=x+y; i++){
// O(1)
// O(y)
}
return; // O(1)
}Now O(1) + O(y) = O(y) so we can combine those successive costs.
public static long dominoes(long x, long y){
// O(1)
for(long i=0; i<=x+y; i++){
// O(y)
}
return; // O(1)
}Now the outer loop runs x+y times. The interior costs O(y) time. So the cost of the loop is O(x+y) * O(y) = O((x+y)*y).
public static long dominoes(long x, long y){
// O(1)
// O((x+y)*y)
return; // O(1)
}And O(1) + O((x+y)*y) + O(1) = O((x+y)*y).
public static long dominoes(long x, long y){
// O((x+y)*y)
}And we're done.
Ignoring the swap that we decided to ignore, the cost is O((x+y)*y). But the truth is that after the swap, if it happens or not, the variable x will contain the minimum of the x and y parameters, and y will contain the maximum. So, accounting for the swap, the running time is O((min(x,y) + max(x,y)) * max(x,y)).
Are we done? We could be. But it's useful to simplify our answer. Note that 1*max(x,y) <= (min(x,y) + max(x,y)) <= 2*max(x,y). Therefore, max(x,y)^2 <= (min(x,y)+max(x,y))*max(x,y) <= 2*max(x,y)^2.
So (min(x,y)+max(x,y))*max(x,y) is Theta(max(x,y)^2) (which is a way to say the two functions are O of one another). This means we can say our function is O(max(x,y)^2) without losing any information.
Like, we could say our function is O(max(x,y)^3), and we'd lose information -- because it's a weaker bound. The fact that (min(x,y) + max(x,y))*max(x,y) is Theta(max(x,y)) means that O(max(x,y)^2) is as strong a bound.
All my posts may be redistributed under the GNU Free Documentation License.
0
#5 22 Days Ago
Rashakil Fol, thanks alot for your explanation. I've managed to determine the time complexity of iterative algorithms but I'm still having problems with recursion. What is the correct way to determine the time complexity of recursion?
Recursion 1:
Recursion 2:
Recursion 1:
public static long rec1(long x, long y){
if(y == 0){
return 1;
}
if(y == x){
return 1;
}
return rec1(x-1, y-1) + rec1(x-1, y);
}Recursion 2:
public static long rec2(long n){
if(n == 0){
return 0;
}
else if(n == 1){
return 1;
}
else{
return 2*rec2(n-1) + rec2(n-2);
}
} •
•
Join Date: Jun 2005
Posts: 2,047
Reputation:
Solved Threads: 139
3
#6 22 Days Ago
Create a recursive formula for the time complexity and figure it out from there.
All my posts may be redistributed under the GNU Free Documentation License.
0
#7 21 Days Ago
•
•
•
•
Originally Posted by Rashakil Fol
Create a recursive formula for the time complexity and figure it out from there.
•
•
Join Date: Jun 2005
Posts: 2,047
Reputation:
Solved Threads: 139
3
#8 20 Days Ago
For example, suppose you have a function
We want to measure its cost. But before we do so, we'll say that its cost is O(t(n)) so that we can use it in the formula.
So t(0) = O(1) and t(n) = O(1) + t(n-1)
int f(int n) {
if (n == 0) {
return 1;
}
else {
return n * f(n-1);
}
} if (n == 0) { // O(1) conditional test
// O(1)
}
else {
// O(1) + t(n-1)
return n * f(n-1);
}So t(0) = O(1) and t(n) = O(1) + t(n-1)
All my posts may be redistributed under the GNU Free Documentation License.
 |
Similar Threads
- Time complexity of algorithm (Computer Science)
- calculate time complexity of the algorithm (Computer Science)
- Time Complexity Problem -Urgent (Computer Science)
- I hit a brick wall-- time complexity problem (Computer Science)
Other Threads in the Computer Science Forum
- Previous Thread: How many instructions are theoretically possible?
- Next Thread: Networking issue (remoting and push technology)
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Latest Computer Science Posts
- Today's Posts
- Unanswered Threads
Related Forum Features
ai algorithm algorithms amazon assignment assignmenthelp assignments battery bigbrother binary bittorrent bletchleypark blogging bomb business codebreaker compiler computer computers computerscience computertrackingsoftware connect conversion csc data dataanalysis dataintepretation development dfa dissertation dissertations dissertationthesis dissertationtopic ebook employment energy extensions floatingpoint foreclosure foreclosuresoftware fuel gadgets geeks givemetehcodez government graphics hardware history homeowners homeworkassignment homeworkhelp humor ibm idea ideas internet ipod itcontracts jobs kindle laser laws linkbait lsmeans mainframes marketing mining mobileapplication msaccess nano networking news os p2p piracy piratebay principles programming rasterizer sam-being-cute sas science security simulation software spying sql stephenfry study supercomputer supercomputing sweden technology textfield turingtest two'scompliment uk virus warehouse ww2
