Big O Notation for all Java Collections

Big O of Java Collections

All credit goes to Kunal saxena.

Resource Link: https://www.linkedin.com/pulse/big-o-java-collections-kunal-saxena/

Data Structure and algorithm links

1. https://www.youtube.com/watch?v=Pn874kEc3IA
2. http://cs.fit.edu/~ryan/java/programs/graph/Prim-java.html
3. http://theoryofprogramming.com/2015/03/27/prims-algorithm/
4. https://stackoverflow.com/questions/18009158/i-want-to-write-a-prims-algorithm-in-java
5. https://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/graph/Prim.java
6. http://sourcecodesforfree.blogspot.in/2013/05/10-prims-algorithm.html
7. http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
8. http://www.geeksforgeeks.org/?p=26604
9. http://www.geeksforgeeks.org/?p=11110
10. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf
11. http://www.ics.uci.edu/~eppstein/161/960206.html
12. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/prim2.html
13. http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Levitin/Contents.htm
14. http://ind.ntou.edu.tw/~litsnow/al98/pdf/Algorithm-Ch6-Heapsort.pdf
15. http://ind.ntou.edu.tw/~litsnow/al98/
16. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/
17. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
18. http://theoryapp.com/selection-insertion-and-bubble-sort/
19. http://farenda.com/algorithms-and-data-structures/

Best tutorial (for C programmer):

1. http://btechsmartclass.com/DS/U2_T9.html

Algorithms are here

http://www.marufnotes.com/

Time Complexity learning at a glance

Time Complexity learning at a glance:

Time complexity	Name	Example
1	Constant	Adding an element to the front of a linked list
logn	Logarithmic	Finding an element in a sorted array
n	Linear	Finding an element in an unsorted array
nlogn	Linear Logarithmic	Sorting n items by „divide-and-conquer‟-Mergesort
n^2	Quadratic	Shortest path between two nodes in a graph
n^3	Cubic	Matrix Multiplication
2^n	Exponential	The Towers of Hanoi problem

Resource Link: http://www.techtud.com/sites/default/files/public/share/algorithm-book-by-karumanchi.pdf

CountryMan

1. http://stackoverflow.com/users/245679/md-sayem-ahmed
2. https://github.com/sayembd/cs-video-courses

Data Structure:

==============

1. Linked Lists

2. Trees,Tries, &Graphs

3. Stacks & Queues

4. Heaps

5. Vectors/ Arraylists

6. Hash Tables

Algorithm:

==========

1. Breadth-First Search

2. Depth-First Search

3. Binary Search

4. Merge Sort

5. Quick Sort

Concepts:

=========

1. Bit Manipulation

2. Memory (Stack vs. Heap)

3. Recursion

4. Dynamic Programming

5. Big O Time & Space

Mathmatics preparation

Permutations and Combinations(5 set with answers)

1. http://www.careerbless.com/aptitude/qa/permutations_combinations2.php
2. http://staff.argyll.epsb.ca/jreed/math30p/perms_combs/permutations.htm

Algorithm lists. You have to know

Even though we are the same codeforces color >.<, i still have valuable advice to provide. My red friends on codeforces have stuck to this method. I have used this also to make the gold division in USACO.
Step 1: Learn and Practice Algorithms
Start from some simple and basic algorithms and practice them thoroughly:
-Sorting
-Scanline (Sweep line)
-traversals
-binary search
-MST/shortest paths
-DP
-Simple data structures:
-dsu, sets, map, heap, queue, stack, deque
Then proceed on to more devious and complex algorithms:
-Greedy
-DAGs, SSCs, Bi-connected compnents
-DP + caching previous results
-compression
-Convex Hull
-Complex Data structures:
-segment trees, linked list, BIT, Trie, Splay, Suffix Trees
-KMP/String hashing/string algorithms
-mincut/maxflow/maxmatching
Step 2: Look at Problems, Know what type of problem it is
I suggest you turn off the tags for unsolved problems so you can try to decide what type of problem you are solving.
At this step, you should try to: -know how to turn this problem into something familiar, into a graph? How will you handle updates? queries?
-know how to handle constraints of the problem. Do you need to add more states?
-Make observations about the problem, if the problem gives huge constraints like 10^6 and then suddenly gives a small constraint of 10, you should take advantage of that. Of course there are many different observations that you can make to help you solve problems.
Note at this step you do not need to necessarily code up the solution, you just need to form a clear approach in your mind.
Step 3: Implementation
Here is when you need to not only recognize the type of problem, but also know how to implement it. This is what I am bad at. My suggestions are:

1. order the codeforces problemset by solved and burn through the first 4~5 pages. I have finished the first 3 already.
2. Practice problems that require more than a direct approach. These problems can combine algorithms like dp with complex data structures, here is an example: http://www.usaco.org/index.php?page=viewproblem2&cpid=365

Other Tips:
When doing codeforces problems, if you get a wrong answer during practice, try not to scroll through the test data to see what you got wrong. Try to test your code again and see if you can fix your bug, this really helps during a contest. This is how I can recover from hacks. Do not only do codeforces (although I think codeforces's problemset is the best), do other sites that have even more archive of problems like POJ, SPOJ, USACO / USACO Training Gateway, etc.

Hope this helps! Trust me, this is how I got into USACO Gold! Just follow this list!

Resource Link: http://codeforces.com/blog/entry/2332#comment-176240

For Algorithm learning, which things I should know ?

We should learn first for beginners:

• Reading in data from standard input (the console), or from a file. You must learn how to do this, since that's how interaction with the program is done.
• Basic arithmetic operations with integer numbers as well as real numbers.
• Basic operations with strings, like extracting a substring or reversing the string entirely.
• Arrays, iterating over an array, updating elements in an array
• .As you get more experience, you can learn about more advanced data structures. Vector, priority queue, map, and set are some of them. 

Resource Link: https://www.quora.com/For-an-ACM-ICPC-beginner-how-should-I-start

Algorithm search optimization

1. https://vimeo.com/15162831
2. http://codeforces.com/blog/entry/18016
3. http://acmproblemsolution.blogspot.com/ 

Algorithm Book Download

1. https://www.youtube.com/watch?v=uxWlxhrwRkA
2. http://www.springer.com/us/book/9781848000698
3. https://github.com/haseebr/competitive-programming/blob/master/Materials/backtracking/bt1.pdf

Palindrome Algorithm Details

Analysis

This problem can be trivially solved by looping through each character and checking it against the character on the opposite side. There is a problem with this though because half the work being done is redundant as it’s checking all characters two times. Consider the palindrome "madam", this algorithm would make the following comparisons:

m ↔ m
a ↔ a
d ↔ d
a ↔ a
m ↔ m

All that needs to be compared to prove it’s a palindrome are the first two characters against the last two since the middle one does not need to be checked:

m ↔ m
a ↔ a

This leads us to our initial solution:

function isPalindrome (text)
  if text is null
    return false
  left ← 0
  right ← text.length - 1
  while (left < right)
    if text[left] is not text[right]
      return false
    left ← left + 1
    right ← right - 1
  return true

Resource Link:

 http://www.growingwiththeweb.com/2014/02/determine-if-a-string-is-a-palindrome.html 

2. http://www.growingwiththeweb.com/2012/11/big-o-notation.html

Minimum Spanning Tree tutorial

https://www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf
https://www-m9.ma.tum.de/graph-algorithms/mst-prim/index_en.html
http://www.stoimen.com/blog/2012/11/19/computer-algorithms-prims-minimum-spanning-tree/

Space Complexity

1. http://www.c-sharpcorner.com/forums/how-to-calculate-algorithm-time-complexity-and-space-complexity
2. http://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html
3. https://www.quora.com/How-do-we-calculate-space-time-complexity-of-an-algorithm
4. http://www.leda-tutorial.org/en/official/ch02s02s03.html

Best Time Complexity Calculation

What are some easy ways to understand and calculate the time complexity of algorithms?

You'd already be aware of Big-O and Theta notations. Big O gives the upperbound - the worst possible execution time of an algorithm. And Ω is the converse of O, ie, the lowest estimate. Θ is somewhere inbetween.

Big O is the most commonly used term. Most of the time we want to find the maximum time an algorithm would take. Let me show some examples.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

Understanding Time Complexity

Let us consider there's a small piece of code (maybe just a single line) that takes one second on a slow computer. This piece of code will be used on a list of items for processing; something like an array waiting to be searched or sorted.

If you have designed an algorithm that is O(1), it means,
If the array contains just a single item, it will take 1 second.
If array has 10 items, it will still take 1 second to finish with all of them.
If it has 100, again 1 second only.
You see, the algorithm you designed is great even for the large arrays.

Let's proceed to quite larger and practical time complexities. Now you have created a similar algorithm, but in O(n) this time.
If array has one item, it will take 1 second. Still seems okay.
If we have 10 items, it will take 10 seconds. Did you see the difference?
Now it we have 100 items, it will take 100 seconds. Going damn bad.
What will happen to the longer lists?

You would have seen, or even designed many algorithms that are of O(n^2) order.
Again, to process a single item, you take 1 second.
With 10, it will take 100 seconds to process the whole array.
And what if you have 100? It'll take 10000 seconds.
In practical cases we may have really big arrays containing millions of items. Such algorithms may make you wait an eternity.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

Calculating Time Complexity

If there is a single iteration, and the iterative variable is incrementing linearly then it's O(n) e.g.
for(i=0;i<n;i++) //O(n)

for(i=0;i<n;i = i + 4) // still O(n)

If the iterative variable is incremented geometrically, then it's O(log n)
e.g
for(i=1;i<n;i = i * 2) //O(log n)

Note that, the implementations don't have to be using loops, they maybe implemented using recursion.

If there is nested loop, where one has a complexity of O(n) and the other O(logn), then overall complexity is O(nlogn);
e.g
for(i=0;i<n;i++) // O(n)
{
   for(j=1;j<n;j=j*3) // O(log n)
}
//Overall O(nlogn)

This is only a finger cross guideline. In general, you have to have good concept to derive the complexity.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

In the definition we say,  f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) andx0 (e.g., x0 = 5) such that f(x) < cg(x) whenever x > x0. You can have a look at the graph above (from wikipedia). Till point x0, we may not have the straightforward behavior. We are to notice larger numbers. So we keep such a limit.

A small comparison of time complexity orders is in this graph below. You can see how bad the higher orders go. Notice the Y axis is a log scale.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

A great explanation is given by various writers to answer a related question in Stack Exchange. You'll find it interesting.
http://stackoverflow.com/questio...
You should also have a look at
How does one know which notation of time complexity analysis to use?
Graph Reference : http://n0b3l1a.blogspot.in/2010/01/bigo-time-complexity.html
Time Complexity Explanation Reference : http://stackoverflow.com/questio...

All credit goes to Aditya Joshi

Big-O notation explained(Time Complexity)

1. So setting a counter to zero is a constant time operation.

total = 0;
==> O(1)



2. If it's 75, we do 75 operations. In mathematical terms, this means that the time it takes to do something increases linearly with its input. We use a variable to represent the size of the input, which everyone in the industry calls n. So the "loop over the list" function is O(n) where n represents the size of a_list.

for element in a_list:
==> O(n)

3. Checking whether an element is equal to 1 is an O(1) operation

if element == 1:
==> O(1)


4. Next, we increment total by 1. This is like setting total to zero (but you have to do addition first). Addition of one, like equality, is also constant time.

total += 1
==> O(1)

So, For all 4,
--------------
(O(1) + O(n) * (O(1) + O(1))
                         ^^^^^^^^^^^^
(O(2n) + O(1))


In big O, we only care about the biggest "term" here. "Term" is the mathematical word that means "portion of an algebraic statement".

in calculating Big-O, we're only interested in the biggest term: O(2n). Because Big-O only deals in approximation, we drop the 2 entirely, because the difference between 2n and n isn't fundamentally different.


Resource Link:
==============
compare the graph of x^2 vs 2x vs x.

1. http://www.wolframalpha.com/input/?i=plot+x%5E2,+x%5E3,+x%5E4+from+x%3D0+to+10  
2. https://justin.abrah.ms/computer-science/big-o-notation-explained.html

How sieve works? Full procedure

1. http://www.javawithus.com/programs/sieve-of-eratosthenes

Prime Sieve of Eratosthenes: Find all primes smaller than or equal to n.

Sample Code:

package com.rizvi.so;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// Java program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes

class SieveOfEratosthenes {
    void sieveOfEratosthenes(int n) {
        int counter = 0;
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n + 1];
        List<Integer> primeList = new ArrayList<Integer>();
        for (int i = 0; i < n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }

        // Print all prime numbers
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true) {
//                System.out.println(i + " ");
                primeList.add(i);
                counter++;
            }
        }
        // Show the primes from primeList
//        for(Integer primeVal : primeList) {
//            System.out.println(""+primeVal);
//        }

        System.out.println("Total number of primes: " + counter);
        System.out.println("Total number of primeList: " + primeList.size());
    }

    // Driver Program to test above function
    public static void main(String args[]) {
        Scanner asdf = new Scanner(System.in);
        int n = asdf.nextInt();
        long startTime = System.nanoTime();
        System.out.print("Following are the prime numbers ");
        System.out.println("smaller than or equal to " + n);
        SieveOfEratosthenes g = new SieveOfEratosthenes();
        g.sieveOfEratosthenes(n);
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println();
        System.out.println("Total time taken: " + estimatedTime);
    }
}

// This code has been contributed by Amit Khandelwal.
// http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Output:

100000000
Following are the prime numbers smaller than or equal to 100000000
Total number of primes: 5761455
Total number of primeList: 5761455

Total time taken: 8097239106
 

Prime Number Optimization

Sample Code:

package com.rizvi.so;

import java.util.Scanner;

public class PrimeCheck {

    public static void main(String[] args) {
        Scanner inp = new Scanner(System.in);
        PrimeCheck primeChecker = new PrimeCheck();
        System.out.println("Give Input: ");
        int candidate = inp.nextInt();
        System.out.println(candidate+" is prime: "+primeChecker.isPrime(candidate));
    }

    // checks whether an int is prime or not.
    boolean isPrime(int n) {
        // check if n is 2
        if (n == 2)
            return true;
        // check if n is a multiple of 2
        if (n < 2 || n % 2 == 0)
            return false;
        // if not, then just check the odds
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

Output:

Give Input:
31
31 is prime: true

Resource Link:

1. http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html

Algorithm Study

1. https://sites.google.com/site/indy256/algo/arrangements
2. https://www.quora.com/Are-there-any-good-sites-for-learning-algorithm-programming-concepts-every-day-similar-to-the-SAT-question-of-the-day
3. http://www.ideserve.co.in/learn/nth-fibonacci-number#algorithmVisualization
4. https://www.quora.com/What-are-the-best-websites-with-algorithm-practice-problems
5. http://introcs.cs.princeton.edu/java/14array/
6. http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L11-InsSort.htm
7. https://www.dyclassroom.com/sorting-algorithm/merge-sort

Algorithm Lectures

1. http://fpl.cs.depaul.edu/jriely/ds2/extras/lectures/
2. http://stackoverflow.com/users/100020/sdcvvc
3. https://www.utdallas.edu/~chandra/documents/6363/
4. http://stackoverflow.com/a/3628777/2293534 : 4 links are given. Go through those links.