nelsibrun Posted March 8, 2022 Share Posted March 8, 2022 So I'm a little stuck with understanding time complexity for average, worst and best case. Say I have an algorithm that runs on a data structure in O(1) time most of the time, but every log(k) iterations it has to run an O(n) operation. For best case do I assume that it doesn't run the operation and we have O(1). Then for worst we'd assume it does and we have O(n)? What about the average case. If we run the algorithm k times, it has to run an O(n) operation log(k) times, so we have something like log(k) * O(n). Averaging this out over the k iterations we get: (log(k) * O(n)) / k as k tends to infinity this reduces to 0 and I guess we have constant time then? I'm not really sure. When we're talking about complexity in terms of n, I assume n is the size of the data structure the algorithm operates on, but then how does this relate to running the algorithm k times? Sorry if that's a bit of a mess just trying to wrap my head around it. Link to comment Share on other sites More sharing options...

nelsibrun Posted March 22, 2022 Author Share Posted March 22, 2022 On 3/8/2022 at 1:42 PM, nelsibrun said: So I'm a little stuck with understanding time complexity for average, worst and best case. Say I have an algorithm that runs on a data structure in O(1) time most of the time, but every log(k) iterations it has to run an O(n) operation. For best case do I assume that it doesn't run the operation and we have O(1). Then for worst we'd assume it does and we have O(n)? What about the average case. If we run the algorithm k times, it has to run an O(n) operation log(k) times, so we have something like log(k) * O(n). Averaging this out over the k iterations we get: https://getappvalley.com/ https://tutuappx.com/ https://tweakbox.mobi/ (log(k) * O(n)) / k as k tends to infinity this reduces to 0 and I guess we have constant time then? I'm not really sure. When we're talking about complexity in terms of n, I assume n is the size of the data structure the algorithm operates on, but then how does this relate to running the algorithm k times? Sorry if that's a bit of a mess just trying to wrap my head around it. I got this,... Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now