How to find runtime of following algorithm?

Question

I am running Big O but totally lost.

while loop only run N/2 and for loop is also N/2 so it becomes N**2?

Am I thinking correctly?

# Block (a)
sum = 0;
n = N
while n > 0: 
    for i in range(0, n):
        sum += 1;
    n = n // 2

# running times: N/2 * N/2 = N^2/4 >> N^2?

# Block (b)
sum = 0
i = 1
while i < N:
    for j in range(0, i):
        sum += 1
    i = i * 2

# running times: N^2??

# Block (c)
sum = 0
i = 1
while i < N:
    for j in range(0, N):
        sum += 1
    i = i * 2

# running times: N^2??

Dmitrii Bychenko · Accepted Answer · 2020-03-20 15:56:01Z

2

Look at

  n = n // 2

or

  i = i * 2

Division (n = n // 2) reduces n much faster then subtraction (n = n - 1). Your solution O(N**2) would have been correct for n = n - 1; for the division (n = n // 2) we have

  n = N
  while n > 0: 
    for i in range(0, n):
        sum += 1;

    n = n // 2

Let's unwrap outer loop (while n > 0:)

 0..N              - N      items to sum
 0..N / 2          - N/2    items to sum
 0..N / 4          - N/4    items to sum
 ...
 0..N / 2**p       - N/2**p items to sum
 ...
 0..N / 2**(log N) - 1      item  to sum

So we have (upper bound):

 N * (1 + 1/2 + 1/4 + ... 1/2**p + ...) = 2 * N = O(N)

running lime is linear.

edited Mar 20, 2020 at 15:56

answered Mar 20, 2020 at 9:39

Dmitrii Bychenko

188k20 gold badges178 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

travelonly-minyoung Over a year ago

Thank you. how does "0..N - N items to sum ...0..N / 2**(log N) - 1 item to sum" become N * (1 + 1/2 + 1/4 + ... 1/2**p + ...)?

Collectives™ on Stack Overflow

How to find runtime of following algorithm?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related