Given a snipplet of code, how will you determine the complexities in general. I find myself getting very confused with Big O questions. For example, a very simple question:

```
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
```

The TA explained this with something like combinations. Like this is n choose 2 = (n(n-1))/2 = n^2 + 0.5, then remove the constant so it becomes n^2. I can put int test values and try but how does this combination thing come in?

What if theres an if statement? How is the complexity determined?

```
for (int i = 0; i < n; i++) {
if (i % 2 ==0) {
for (int j = i; j < n; j++) { ... }
} else {
for (int j = 0; j < i; j++) { ... }
}
}
```

Then what about recursion …

```
int fib(int a, int b, int n) {
if (n == 3) {
return a + b;
} else {
return fib(b, a+b, n-1);
}
}
```

### More Related Questions

- Is log(n!) = Θ(n·log(n))? This is a homework question. I'm not expecting an answer, just some guidance, possibly :) I am to show that log(n!) = Θ(n·log(n)).
A hint was given that I should show the upper bound […]
- Whats the time complexity of this algorithm for Palindrome Partitioning? Palindrome Partitioning
Given a string s, partition s such that every substring of the
partition is a palindrome. Return all possible palindrome
partitioning of s.
Personally I […]
- all solutions to change making with dynamic programming I was reviewing my handouts for our algorithm class and I started to think about this question:
Given different types of coins with different values, find all coin configurations to add […]
- Is this algorithm linear? Inspired by these two questions: String manipulation: calculate the "similarity of a string with its suffixes" and Program execution varies as the I/P size increases beyond 5 in […]
- Whats the best way to model recurring events in a calendar application? I'm building a group calendar application that needs to support recurring events, but all the solutions I've come up with to handle these events seem like a hack. I can limit how far ahead […]
- Is the time complexity of the empty algorithm O(0)? So given the following program:
Is the time complexity of this program O(0)? In other words, is 0 O(0)?
I thought answering this in a separate question would shed some light on this […]
- How to avoid StackOverflowError caused by the number of recursion calls in Java? I want to solve this problem: https://www.hackerrank.com/challenges/find-median ,i.e. find the median element in unsorted array. To do this I perform quickselect algorithm. My program […]
- What does O(log n) mean exactly? I am currently learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the […]
- Trace a recursive coin change algorithm I am trying to trace this recursive algorithm of the coin change problem with M=10, c={5,3,1} and d=3. M is the value of money for which change is required, c is the different coin values […]
- How to merge two sorted arrays into a sorted array? This was asked of me in an interview and this is the solution i provided:
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j […]