CODEWITHSUNDEEP
algorithmtime-complexity
mascai
mascai

Reputation: 1852

What is the loops time complexity?

I want to identify the time complexity of the loops below.

Are these the right thoughts about time complexity?

Loop 1

for (auto i = 1; n > 0; n -= i, i +=2) {}

My thoughts: O(n)

Because i has only linear changes and if n --> +infinity, then n-i doesn't matter.

Loop 2

for (auto i = 1; n > 0; n -= i, i += i / 2) {}

My thoughts: O(n)

Because we have a geometric progression of i:

i_n = i_1 *(3/2)^(n - 1)

Upvotes: 0

Views: 65

Answers (1)

trincot
trincot

Reputation: 350137

The first is O(√𝑛)

Let's first rewrite it to not change 𝑛, as that is confusing. Let's introduce 𝑚 to take that changing role:

for (auto i = 1, m = n; m > 0; m -= i, i +=2) {}

𝑖 follows the sequence 1, 3, 5, 7, ...

After 𝑘 iterations:

      𝑚 = 𝑛−∑𝑘𝑖=1(2𝑖−1)

which is (by Wikipedia):

      𝑛−𝑘²

The loop ends when 𝑛−𝑘²≤0, i.e. when √𝑛≤𝑘. As 𝑘 is a measure of the time complexity, we have O(√𝑛)

The second is O(log𝑛)

The value of 𝑖 will indeed follow a geometric sequence. Let's again introduce 𝑚 as the changing value (instead of 𝑛), then when 𝑘 iterations have been made:

      𝑚=𝑛−∑𝑘𝑖=1(3/2)𝑖,

which is (by Wikipedia):

      𝑚=𝑛−((3/2)𝑘+1−1)/((3/2)−1)

      𝑚=𝑛−2((3/2)𝑘+1−1)

The loop ends when 𝑛−2((3/2)𝑘+1−1)≤0, or

      𝑛/2+1≤(3/2)𝑘+1, or

      log1.5(𝑛/2+1)≤k+1

Since 𝑘 is a measure of the time complexity, we have O(log𝑛).

Upvotes: 1

Related Questions