Java - Comparing efficiency of two O(n) algorithms

Question

I'm studying Linked Lists and the question is - Write a function to print the middle term of a given linked list (assume that LL has odd number of nodes).

Method 1 - Traverse the LL and count the number of nodes using a counter. Add 1 (to make it an even number) and divide the counter by 2 (ignore math for discrepancies). Traverse the LL again but this time only upto the counter-th term and return.

void GetMiddleTermMethod1(){
            //Count the number of nodes
            int counter = 0;
            Node n = FirstNode;
            while (n.next != null){
                counter = counter + 1;
                n = n.next;             
            }
            counter=counter+1/2;
            //now counter is equal to the half of the number of nodes

            //now a loop to return the nth term of a LL 
            Node temp = FirstNode;
            for(int i=2; i<=counter; i++){
                temp = temp.next;
            }
            System.out.println(temp.data);
        }

Method 2 - Initialize 2 references to nodes. One traverses 2 nodes at a time and the other only traverses 1. When the fast reference reaches null (the end of LL), the slow one would have reached the middle and return.

void GetMiddleTermMethod2(){
            Node n = FirstNode;
            Node mid = FirstNode;
            while(n.next != null){
                n = n.next.next;
                mid = mid.next;
            }
            System.out.println(mid.next.data);
        }

I have 3 questions -

Q1 - How can I know which algorithm is more efficient in case I'm asked this question in a job interview? I mean both functions traverse the LL one and a half times (second one does it in one loop instead of 2 but still its traverses the LL one and a half times)...

Q2 - Since both algorithms have the Big O of O(n), what parameters will decide which one is more efficient?

Q3 - What is the general method of calculating the efficiency of such algorithms? I'd really appreciate If you could link me towards the suitable tutorial...

Thanks

Answer 1

Well, there is no real simple answer for that, the answer may differ on the compiler optimization, JIT optimization, and the actual machine that runs the program (which might be optimized better for one algorithm for some reason).

The truth is, other than the theoretical big O notation that gives us asymptotic behavior, there is seldom a "clean, theoretical" way to determine Algorithm A is faster than Algorithm B in conditions (1),(2),...,(k).

However, it doesn't mean there is nothing you can do, you can benchmark the code by creating various random data sets, and time the duration each algorithm takes. It is very important to do it more than once. How much more? Until you get a statistical significance, when using some known and accepted statistical test, such as Wilcoxon signed ranked test.

In addition, in many cases, insignificant performance usually doesn't worth the time spent to optimize the code, and it would be even worse if it makes the code less readable - and thus harder to maintain.