CODEWITHSUNDEEP
time-complexity
user5005768Himadree
user5005768Himadree

Reputation: 1427

Run Time Analysis: Correct my examples on Why these loops have O(log n) Time Complexity

I was doing analysis of loops and got these following loops:

for (int i = 1; i <=n; i *= c) {
       // some expressions
   }

 for (int i = n; i > 0; i /= c) {
       // some expressions
   }

I understand that the loop growth rate is log n (base c) But I am stuck while doing some test examples such as below:

Loop-1: if c = 2 and n = 8 then

loop runs true for i= 1,2,4,8 (4 times) BUT log 8 = 3 ? [should be 4]

Loop-2: if c = 2 and n = 8 then

loop runs true for i= 8,4,2,1 (4 times) BUT log 8 = 3 ? [should be 4]

Where i did the mistake.please help me to match the results with Time rate Log n. Thanks

Upvotes: 1

Views: 361

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Here is the best possible answer from an academic reference:

enter image description here

Source: http://faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit03_ComplexityAnalysis1.ppt

Upvotes: 1

apomene
apomene

Reputation: 14389

O notation is always an approximation, or better a worst case limit. For example O(logN)=O(logN+X), when X is a constant. In your example the precise iterations of your for loop is logN+1, which means it is O(logN+1)=O(logN).

Upvotes: 1

Related Questions