CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
Soner from The Ottoman Empire
Soner from The Ottoman Empire

Reputation: 20891

Time complexities of the given loops O(logn) or O(n)

//loop1
for (int i = 1; i <= n; i*=2) { }
//loop2
for (int i = 1; i <= logn; i++) { }

We argue with my friend about the loops that I think the first one is O(logn) and the latter is O(n). However, for the latter one he says it is also O(logn) not O(n).

Could you explain?

Upvotes: 2

Views: 6295

Answers (2)

displayName
displayName

Reputation: 14389

Short Answer:

Both are Log (n) because, for an input n, both the loops will run for Log (n) times.

While the first loop runs Log (n) times because of i *= 2 in the for-loop, the second loop runs Log (n) times because of the upper limit in the for-loop set directly to that value.

Detailed:

Big-O tells the Rate of Growth of a function. The second loop - which is the one you are confused about - is actually simpler of the two loops. You can see directly that for any input n, the function will always take time proportional to Log (n) only.

Hence the rate of growth of the second loop is proportional to Log (n) or in other words, equal to O(Log (n)).

Upvotes: 4

nice_dev
nice_dev

Reputation: 17805

Whenever in doubt, just substitute values of n with some values and dry run both loops.

Let's take n = 100 for example.

//loop1

for (int i = 1; i <= n; i*=2) { }

Steps(in the form of i,n) are:

  • 1 , 100
  • 2 , 100
  • 4 , 100
  • 8 , 100
  • 16 , 100
  • 32 , 100
  • 64 , 100
  • 128 , 100

Technically, it solves in 7 steps.

//loop2

for (int i = 1; i <= logn; i++) { }

  • log2(100) = 6.64 ~ 7.
  • Steps(in the form of i,n) are:
    • 1 , 7
    • 2 , 7
    • 3 , 7
    • 4 , 7
    • 5 , 7
    • 6 , 7
    • 7 , 7
    • 8 , 7

This also gets solved in 7 steps. Hence, both approaches have same complexity which is O (log(n)).

Upvotes: 6

Related Questions