# CodeStepByStep

## bigoh8

Language/Type: Java algorithm analysis big-oh

Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N. In other words, write the code's growth rate as N grows. Write a simple expression that gives only a power of N using a caret `^` character for exponentiation, such as `O(N^2)` to represent O(N2) or `O(log N)` to represent O(log2 N). Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14).

 ```// a) int sum = 0; for (int i = 0; i < 1000; i++) { for (int j = 1; j < N * 2; j++) { sum++; } for (int k = 0; k < i; k++) { sum++; } } System.out.println(sum);``` answer: ```// b) ArrayList v = new ArrayList(); for (int i = 0; i < N; i++) { v.add(0, i); } while (!v.isEmpty()) { v.remove(0); } System.out.println("done!");``` answer: ```// c) Queue queue = new LinkedList(); for (int i = 1; i <= N; i++) { queue.add(i * i); } TreeMap map = new TreeMap(); while (!queue.isEmpty()) { int k = queue.remove(); map.put(k, N * N); } System.out.println("done!");``` answer: ```// d) HashSet set = new HashSet(); for (int i = 0; i < N; i++) { set.add(i); } Stack stack = new Stack(); for (int i = 0; i < N * N; i++) { stack.push(i); } for (int i = 0; i < N; i++) { set.remove(i); stack.pop(); } System.out.println("done!");``` answer: ```// e) ArrayList v = new ArrayList(); for (int i = 1; i <= 1000000000; i++) { v.add(i); } v.clear(); System.out.println("done!");``` answer: