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
``````

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)

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

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
}
``````