0

I'm studying algorithm's complexity and I'm still not able to determine the complexity of some algorithms ... Ok I'm able to figure out basic O(N) and O(N^2) loops but I'm having some difficult in routines like this one:

// What is time complexity of fun()? int fun(int n) { int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count; }

Ok I know that some guys can calculate this with the eyes closed but I would love to to see a "step" by "step" how to if possible.

My first attempt to solve this would be to "simulate" an input and put the values in some sort of table, like below:

for n = 100 Step i 1 100 2 50 3 25 4 12 5 6 6 3 7 1

Ok at this point I'm assuming that this loop is O(logn), but unfortunately as I said no one solve this problem "step" by "step" so in the end I have no clue at all of what was done ....

In case of the inner loop I can build some sort of table like below:

for n = 100 Step i j 1 100 0..99 2 50 0..49 3 25 0..24 4 12 0..11 5 6 0..5 6 3 0..2 7 1 0..0

I can see that both loops are decreasing and I suppose a formula can be derived based on data above ...

Could someone clarify this problem? (The Answer is O(n))

rotaran
  • 59
  • 2
  • 10
  • Simulating it can give you intuition, but the only way to get a definitive answer is to derive it analytically. – Oliver Charlesworth Apr 06 '17 at 19:43
  • Yes I understand ... but how can I know step by step that this algorithm is O(n) ? – rotaran Apr 06 '17 at 19:51
  • 1
    You've already count the number of operations. It's n + n/2 + n/4 + ... + 1. `n + n/2 + n/4 + ... + 1` <= `n * SUM(1 / 2^k), for k = [0,inf)` <= `n*2` ∈ `O(n)` – DAle Apr 06 '17 at 20:03
  • If you continually divide any number by `x`, you will get to 0 in `logx(n)` steps. So if you divide 1000 continually by 3, it'll take log-base-3(1000) steps to get to 0. And your inner loop does `n + n/2 + n/4 + n/8 + n/16 ...` iterations. That series has a limit of 2n. So your inner loop does at most 2n iterations, which makes it O(n). – Jim Mischel Apr 06 '17 at 20:03
  • Thanks @Dale, now I can understand the outer loop, If I perform some substitution it will become: 100 + 100/2 + 100/4 + 100/8 ... => 100 + 50 + 25 + 12 (very similar to my table). My doubt now is about the inner loop ... I learnt that I need to "multiply" the outer loop for the inner loop but In this case what is the derived formula for the inner loop? Thanks – rotaran Apr 06 '17 at 20:18

2 Answers2

1

Lets break this analysis up into a few steps.

First, start with the inner for loop. It is straightforward to see that this takes exactly i steps.

Next, think about which different values i will assume over the course of the algorithm. To start, consider the case where n is some power of 2. In this case, i starts at n, then n/2, then n/4, etc., until it reaches 1, and finally 0 and terminates. Because the inner loop takes i steps each time, then the total number of steps of fun(n) in this case is exactly n + n/2 + n/4 + ... + 1 = 2n - 1.

Lastly, convince yourself this generalizes to non-powers of 2. Given an input n, find smallest power of 2 greater than n and call it m. Clearly, n < m < 2n, so fun(n) takes less than 2m - 1 steps which is less than 4n - 1. Thus fun(n) is O(n).

andrew
  • 2,524
  • 2
  • 24
  • 36
1

Another simple way to probably look at it is:

Your outer loop initializes i (can be considered step/iterator) at n and divides i by 2 after every iteration. Hence, it executes the i/2 statement log2(n) times. So, a way to think about it is, your outer loop run log2(n) times. Whenever you divide a number by a base continuously till it reaches 0, you effectively do this division log number of times. Hence, outer loop is O(log-base-2 n)

Your inner loop iterates j (now the iterator or the step) from 0 to i every iteration of outer loop. i takes the maximum value of n, hence the longest run that your inner loop will have will be from 0 to n. Thus, it is O(n).

Now, your program runs like this:

Run 1: i = n, j = 0->n
Run 2: i = n/2, j = 0->n/2
Run 3: i = n/4, j = 0->n/4
.
.
.
Run x: i = n/(2^(x-1)), j = 0->[n/(2^(x-1))]

Now, runnning time always "multiplies" for nested loops, so O(log-base-2 n)*O(n) gives O(n) for your entire code

Tejash Desai
  • 466
  • 4
  • 11