CODEWITHSUNDEEP
algorithmperformancetimewhile-loopcode-analysis
user3495690
user3495690

Reputation: 576

Easiest way to calculate time complexity?

I find it pretty easy to calculate the time complexity for most problems, but my prof gives really complicated examples and I have trouble figuring them out. Here are two that he's given us that I couldn't get to the bottom of:

Example 1:

x = 0
j = n
while (j >= 1)
    for i = 1 to j do
        x += 1
    j *= 3/4
return x

Example2:

x = 0
j = 3
while (j <= n)
    x += 1
    j *= j
return x

Please note that for operations like x += 1 and j *= j, we only count this as 1 time unit.

If you could show me how you would calculate the time complexity for these examples, I should be able to deduce how I would do it for most of the ones he gives. Thanks!

Upvotes: 0

Views: 361

Answers (1)

vish4071
vish4071

Reputation: 5277

Answers:

1. O(j)
2. O(log log(n))

Explanation:

  1. See the inner loop. It operates j times in the 1st entry. Now, j=3j/4. So, second time, it operates 3j/4 times. 3rd time, 9j/16, and so on. The total number of operations will be:

    j + 3j/4 + 9j/16 + ... = 4j

So, complexity will be O(4*j) = O(j).

  1. There is only one loop. The value of its controller (j) increases as:

    3, 9, 81, 6561, ...

Now, the number of iterations it will make until it reaches a certain number n will be log log (n). If it increased by a multiple of 3 everytime, like:

3, 9, 27, 81, 243...

the complexity would have been O(log n).

Upvotes: 3

Related Questions