Understanding O(log n) & O(n) problems

[ibthevivin]

For each part (A) (D) below, clearly indicate whether the runtime is O(log n) or O(n). Can someone please explain how this works?

public class Q9f 
    {
    public static void main(String[] args) 
        {
        int n = ...;
        int[] a = new int[n]; 

        // (A)
        for (int index = 0; index < a.length; ++index)
            a[index] = index; 

        // (B)
        int index = 1;
        while (index < n) 
            {
            a[index] = a[index] + a[index-1];
            index *= 2; // index is doubled
            }

        // (C)
        for (int value: a)
            System.out.println(value);

        // (D)
        index = n-1;
        while (index > 0) 
            {
            a[index] += 1; // add 1 to a[index]
            index /= 2;
            }
        } // main()
    } // class Q9f

[cmps]

Hello ... I think all of these are O(n)
O(n) is when you have 1 for loop or while loop
if you for loop inside a for loop u will get a O(n^2)
and every time you put for loop inside another you will increment the power number
ex:

O(n)for(){} 
O(n^2)for(){for(){}} 
O(n^3) for(){for(){for(){}}} 
O(n^4) for(){for(){for(){for(){}}}}

if you have 2 for loops but not one inside the other, you will get O(2n) which is concidered as O(n).
Examples

O(3n) for(){} for(){} for(){}
O(2n) for(){} for(){}

The above examples are concidered O(n)
Formula: O(#n) = O(n)

[JamesCherrill]

Look again at the loops where a value is being doubled or halved... ;)

[mvmalderen]

Hello ... I think all of these are O(n)

That's not true, take a look at (B) and (D), where the index is divided by / multiplied by two. These are O(log(n)).

This is O(n):

int index = 1;
while (index < n) 
{
    ...
    index++ // index is incremented
}

This is O(log(n)):

int index = 1;
while (index < n) 
{
    ...
    index *= 2; // index is doubled
}