CODEWITHSUNDEEP
algorithmbig-o
Zak
Zak

Reputation: 1154

Big-O time complexity, nested for and while loop

I am trying to understand Big-O Time complexity and am unfortunately struggling, I cannot seem to grasp the concept, I know my results are correct for the following two code fragments however how I got there seems to be wrong. Would someone be able to help explain where I'm mis-understanding (not please, however not using sigma. Thank you!

Code Fragment               Time Complexity
sum ← 0                     O(1)
  for i ← 1 to n do         O(n)
    for j ← 1 to n do       O(n)
      k←1                   O(1)
      while k < n do        
        k ← k * C           O(log n)  - affected by C (due to multiplication)
        sum ← sum + 1       O(1)
                            -----------
                            O(1 x n x n x 1 x [log n] x 1)
                            O(n2 log n)

Code Fragment             Time Complexity
sum ← 0                   O(1)
 for i ← 1 to n do        O(n)
  for j ← 1 to i do       O(n) 
    k←1                   O(1)
    while k < n do      
      k ← k + C           O(n) – not affected by C, k is arbitrarily large
      sum ← sum + 1       O(1)
                            -----------
                          O(1 x n x n x 1 x n x 1)
                          O(n^3)

Upvotes: 0

Views: 8083

Answers (1)

Eran
Eran

Reputation: 393841

I see minor errors in the computation, though the final results are correct.

In the first algorithm :

O(1 x n x n x 1 x [log n] x 1)

should be 

1 + n x n x (1 + (O(log n) x 2)) = O(n^2 * log n)

In the second algorithm :

O(1 x n x n x 1 x n x 1)

should be 

1 + n x O(n) x (1 + (O(n) x 2)) = O(n^3)

Upvotes: 3

Related Questions