There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.
big o notation for reading data in blocks
Hi,
If there is a file of p bytes (characters), you would take O(p) time to read the file. But, if you read the file in blocks of size o, would the big o notation for the time complexity be O((p/o)*p)?
Thanks a lot
If there is a file of p bytes (characters), you would take O(p) time to read the file. But, if you read the file in blocks of size o, would the big o notation for the time complexity be O((p/o)*p)?
Thanks a lot
Asked:
-
7
6
- +1
3 Solutions
LVL 85
Unlikely, but it may be conceivable that some implementation could have been written to behave that way.
I did a program that read the first o characters and then the second o characters. But, I am not sure of the complexity. To read the entire file, you would use p/o blocks. So, the complexity is (p/o)*p. However, I am not sure if this is correct for this implementation. Thanks a lot.
The time to read the first o characters is O(o).
The time to read the second o characters is O(o)
The time to read the last o characters is O(o).
At first, I thought, it should be added. O(o)+O(o) which gives O(p). But, sometimes, I see people put the number of blocks or the number of rounds that is required to read the entire O(p). So, p/o gives you the number of blocks or rounds. So, you need p/o rounds or blocks to read the entire file. I see, you don't times with p but with o. That is, (p/o)*o. So, it is O(p) I think.
I understand that constant is ignored. p/o looks like a constant but it would given different values for different data. So, it can be considered a variable. That is the reason, I am multipying with p/o...
The time to read the second o characters is O(o)
The time to read the last o characters is O(o).
At first, I thought, it should be added. O(o)+O(o) which gives O(p). But, sometimes, I see people put the number of blocks or the number of rounds that is required to read the entire O(p). So, p/o gives you the number of blocks or rounds. So, you need p/o rounds or blocks to read the entire file. I see, you don't times with p but with o. That is, (p/o)*o. So, it is O(p) I think.
I understand that constant is ignored. p/o looks like a constant but it would given different values for different data. So, it can be considered a variable. That is the reason, I am multipying with p/o...
Sorry ozo, that is what I wrote and then, I realise that it is o^2.
This means that the big o notation is very simple. That is, O(p). It doesn't matter whether you read the files in blocks or at once.
Sorry for sounding stupid. p/o is a variable (and not a constant) because it gives a different value for different files. But, it would give similar value for the same input file. Did I understand this wrong ?
This means that the big o notation is very simple. That is, O(p). It doesn't matter whether you read the files in blocks or at once.
Sorry for sounding stupid. p/o is a variable (and not a constant) because it gives a different value for different files. But, it would give similar value for the same input file. Did I understand this wrong ?
What if you try using actual values for demonstration?
Let's say you have a file of length 10 bytes (p). If you read 1 byte at a time, then you have 10 rounds, and that would be O(p). If you now break that up into 2 byte chunks (o), you now have 5 rounds. Since it takes 5 rounds to read the file, should the overall time not be O(p/o)--the overall size of the file divided by the size of the chunk. (I am assuming you're considering the time taken to read a chunk to be constant time, and not factoring in the reading of each byte into the complexity of reading a chunk.) I am not sure why you would want to multiply p or o to the division.
Let's say you have a file of length 10 bytes (p). If you read 1 byte at a time, then you have 10 rounds, and that would be O(p). If you now break that up into 2 byte chunks (o), you now have 5 rounds. Since it takes 5 rounds to read the file, should the overall time not be O(p/o)--the overall size of the file divided by the size of the chunk. (I am assuming you're considering the time taken to read a chunk to be constant time, and not factoring in the reading of each byte into the complexity of reading a chunk.) I am not sure why you would want to multiply p or o to the division.
Hi kaufmed,
I am a newbie in big o notations (I am trying to understand myself). This is what I understand (I may be wrong).
Say o is 5 and p is 10
It takes O(5) to read the first 5 characters
Another O(5) to read the second 5 characters
In total, it takes O(5+5) = O(10)
Now, we can get the same number if take the number of rounds which is 2 here and multply it with O(5) which gives O(10).
The confusion is that you need to ignore the constants but you keep the variables..
I am a newbie in big o notations (I am trying to understand myself). This is what I understand (I may be wrong).
Say o is 5 and p is 10
It takes O(5) to read the first 5 characters
Another O(5) to read the second 5 characters
In total, it takes O(5+5) = O(10)
Now, we can get the same number if take the number of rounds which is 2 here and multply it with O(5) which gives O(10).
The confusion is that you need to ignore the constants but you keep the variables..
O(5) = O(10) = O(1)
Ignoring constants, what happens when p doubles? What happens when o doubles?
What happens when p changes by a factor of 10? 100? 1000000?
Ignoring constants, what happens when p doubles? What happens when o doubles?
What happens when p changes by a factor of 10? 100? 1000000?
If you read a p-byte file one byte at a time, it will take p reads.
If you read a p-byte file o bytes at a time, it will take p/o reads.
But in either case, if the file is 2*p or 10*p it will take 2 or 10 times longer.
Reading is inherently a linear operation, so O(p) would be correct.
If you read a p-byte file o bytes at a time, it will take p/o reads.
But in either case, if the file is 2*p or 10*p it will take 2 or 10 times longer.
Reading is inherently a linear operation, so O(p) would be correct.
I think, i understand now. When p doubles, the time doubles but the doubling is never reflected in the big oh notation.
Question has a verified solution.
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.
Have a better answer? Share it in a comment.
Join & Write a Comment Already a member? Login.
Featured Post
There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.
Tackle projects and never again get stuck behind a technical roadblock.
Join Now