Algorithm Analysis

Question

So I understand a little bit of algorithm analysis, but I'm at a complete loss to understand how to do this one. Can someone please explain this to me? Would this be O(logn)? ``` for (int i=1; i < n; i*=2) for (int j=0; j < i; j++) // do simple operation ```

Accepted Answer

To find the big O of the nested loops, you need to do steps like the following example.

For example, let:

```
n = 10
```

now the outer loop executes 3 time that is:

```
i=2,4 and 8
```

and inner loops executes 3 time for each iteration like

```
i=2 it iterates 2 times
i=4 it iterates 4 times
i=8 it iterates 8 times
```

so the total number of iterations are less the 2*n which makes it O(2n) we can neglect the constant factor so its big O is

```
O(n)
```

Algorithm Analysis

Solution

Problem