1

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:**

```
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;
}
```

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:**

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