CODEWITHSUNDEEP
algorithmruntime
user2789945
user2789945

Reputation: 565

Run time of this specific For loop

I'm working on an algorithms problem, and wanted to check my intuition about the run time of this specific line:

for i= floor(A.heapsize/2)+1 to A.heapsize //iterate through leaves of heap

Where A.heap-size is the same as n, and everything else in the for loop takes constant time. Does the loop run in O(n) time?

Upvotes: 0

Views: 32

Answers (2)

aruisdante
aruisdante

Reputation: 9075

Big-O is not runtime. Runtime can only be determined by benchmarking. Instead, it is is algorithmic complexity; while the two are related (AC effectively defines how RT grows with input size), they are not interchangeable.

Having said that yes, a single for-loop across a range is always O(n). Note that any constant modification (for example, only iterating across half the list) doesn't change the AC of the operation, even though it clearly makes the operation take less time (an example of why AC and RT are not the same); The number of iterations still grows linearly with the value of heapsize.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

Yes, it is O(n). The constant factor is dropped from big-O notation, regardless of whether it's greater than one or less than one. In your case, the constant factor is ½.

Upvotes: 2

Related Questions