CODEWITHSUNDEEP
algorithmbig-o
merry-go-round
merry-go-round

Reputation: 4625

Find the Big-O of the modular algorithm

i=1
while i <= n do:
   j=0
   k=i
   while k%3 == 0 do:
      k = k/3
      j++
   end

   print i, j
   i++
end

What is Big-O of given algorithm (How do we show my work)? And what does this algorithm output // ?

My answer and approach

O(nlogn). Because the outer loop runs linear time as O(n) while the inner loop is dependent as O(logn).

But I'm not sure if it's logn.

When n = 10, 

ij
00
10
20
31
40
50
61
70
80
92
100 ( 10, 0)

When n = 30

i j
1 0
2 0
3 1
4 0
5 0
6 1
7 0
8 0
9 2
10 0
11 0
12 1
13 0
14 0
15 1
16 0
17 0
18 2
19 0
20 0
21 1
22 0
23 0
24 1
25 0
26 0
27 3
28 0
29 0
30 1

Upvotes: 1

Views: 78

Answers (1)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522396

Appreciate that every third number in the series from 1 to n will be divisible by 3. In the worst case, such a number would end up being divided by 3 in the k loop log_3(i) times. So the sequence will behave like O(n) two thirds of the time, and like O(n*log3(n)) one third of the time. We can therefore claim that your code is upper bounded by O(n*log3(n)), although there is a bound which is tighter than this.

The code will print each value i in the series along with the "three depth" of that number. By "three depth" I mean how many times we were able to divide i by 3. Obviously, for i values which are not multiples of 3, the depth is 0.

Upvotes: 4

Related Questions