Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

big o notation for reading data in blocks

Posted on 2013-01-07
15
Medium Priority
?
389 Views
Last Modified: 2013-01-09
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
0
Comment
Question by:zizi21
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
15 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 38753730
Unlikely, but it may be conceivable that some implementation could have been written to behave that way.
0
 

Author Comment

by:zizi21
ID: 38753772
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.
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 1600 total points
ID: 38753794
Do you read the entire file each time you read a block?
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:zizi21
ID: 38753841
Thanks for replying.

I only read a block each time (and not the entire file).
0
 
LVL 84

Expert Comment

by:ozo
ID: 38753926
So what is the time to read the first o characters?
0
 

Author Comment

by:zizi21
ID: 38753986
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...
0
 
LVL 84

Expert Comment

by:ozo
ID: 38754001
That is, (p/o)*o. So, it is O(p/o^2)
Look more carefully.
[Edit: sorry, I see you already did]
0
 

Author Comment

by:zizi21
ID: 38754138
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 ?
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 38754295
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.
0
 

Author Comment

by:zizi21
ID: 38754507
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..
0
 
LVL 84

Accepted Solution

by:
ozo earned 1600 total points
ID: 38754541
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?
0
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 400 total points
ID: 38754829
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.
0
 

Author Comment

by:zizi21
ID: 38757514
Thanks very much for the replies..
0
 

Author Comment

by:zizi21
ID: 38757528
I think, i understand now. When p doubles, the time doubles but the doubling is never reflected in the big oh notation.
0
 
LVL 84

Expert Comment

by:ozo
ID: 38758172
I would say that the doubling is reflected in the big oh notation in the sense that
O(p) implies that when p doubles, the time doubles
0

Featured Post

Tech or Treat!

Submit an article about your scariest tech experience—and the solution—and you’ll be automatically entered to win one of 4 fantastic tech gadgets.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

604 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question