Avatar of zizi21
zizi21
 asked on

Help on big oh analysis

Hi,

I am trying to understand big oh notations. Please correct me.

Say there is a program that accesses a file on disk randomly and say the size of the file n.
So, the big oh notation for this program is O(n) this is because it may access the file randomly at n positions. However, there is a possibility that the program assess the data for the file from the cache but lets ignore this for now.

If the program accesses the file sequantially (one after the other), the big oh notation is O(1).

Is this right ?

Thank you very much.
AlgorithmsC

Avatar of undefined
Last Comment
phoffric

8/22/2022 - Mon
ozo

O(1) time for a single access.
O(n) time to access all of the file.
zizi21

ASKER
Doesn't making random accesses to disk does not make a difference to the big oh notation ?
zizi21

ASKER
Thanks ozo. I thought random accesses influeces big oh notations ?
Your help has saved me hundreds of hours of internet surfing.
fblack61
ozo

It can.  
What disk operations does the program require?
zizi21

ASKER
Thanks ozo.

The program accesses the data on file on random positions...But, how do I write that in big oh notation?
SOLUTION
ozo

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
GET A PERSONALIZED SOLUTION
Ask your own question & get feedback from real experts
Find out why thousands trust the EE community with their toughest problems.
zizi21

ASKER
Thank you very much for the reply.

Does this mean that if seeking gets slower in large files, it is always sqrt(n)? But, why sqrt(n)  and not only other number ? Seeking would get slower in larger files because the files would not be cached in RAM. But, if the file is small, it is cached in RAM and accessing it is fast.

For example, if the size of the file is larger than the available RAM, we can say the file is not cached into RAM. And, in this situation, making random accesses is expensive.
⚡ FREE TRIAL OFFER
Try out a week of full access for free.
Find out why thousands trust the EE community with their toughest problems.
SOLUTION
ozo

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
⚡ FREE TRIAL OFFER
Try out a week of full access for free.
Find out why thousands trust the EE community with their toughest problems.
ASKER CERTIFIED SOLUTION
phoffric

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
⚡ FREE TRIAL OFFER
Try out a week of full access for free.
Find out why thousands trust the EE community with their toughest problems.
zizi21

ASKER
Thank you very much for all the replies. I am studying it now.
zizi21

ASKER
"If you read the data sequentially, it will take twice as long to read the entire file if the data doubles, so sequential reading is also an O(n) operation. "

Thank you very much for your reply. If I understand this correctly, accessing each record of data takes O(1) time (for sequential access) and O(n) for the entire file.
ozo

Under that scenario, reading 1 record is O(1), reading n records is O(n)
I started with Experts Exchange in 2004 and it's been a mainstay of my professional computing life since. It helped me launch a career as a programmer / Oracle data analyst
William Peck
zizi21

ASKER
Thank you very much....
zizi21

ASKER
Thank you .
zizi21

ASKER
I spent days trying to understand and all of you helped lots...Thank you verymuch.
⚡ FREE TRIAL OFFER
Try out a week of full access for free.
Find out why thousands trust the EE community with their toughest problems.
phoffric

For very large files, I was saying that because additional cylinders will result in the average seek time in accessing a single record will increase linearly as the number of cylinders increase, then reading one record is O(n), not O(1).

Suppose a file is small, and that the additional records are placed in the same cylinder. In that case the reading of one records is O(1).