[OCP 17 book] | [OCP 11 book] | [OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
abalfazl hossein wrote:Is there any software or IDE can draw graph for a program?
~ Jeff Yan ~
abalfazl hossein wrote:May you know me these softwares ?
2. linear for loops: O(n)
k=0;
for(i=0; i<n; i++)
k++
For loops are considered n time units because they will repeat a programming statement n times.
The term linear means the for loop increments or decrements by 1
abalfazl hossein wrote:Is it possible to estimate the maximum time that is needed for an algorithm by big O?For example say this code takes 20 sec!>
k=0;
for(i=0; i<n; i++)
k++
For loops are considered n time units because they will repeat a programming statement n times.
The term linear means the for loop increments or decrements by 1
abalfazl hossein wrote:Is it right definition about linear for?
O(N) = as you increase the size of input, the time taken to complete operations scales linearly with that size
Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
abalfazl hossein wrote:
Another question:
It is said the worst case here is : o(n)
Now my question is:
If it is the worst case, Then what can be the average case for this?
>
"If the facts don't fit the theory, get new facts" --Albert Einstein
abalfazl hossein wrote:I see they use big O in order to find the relationship between size on input and time.In fact, I think Big o is a function that represent If size of input being increased, How much time of running of algorithm will be increase. Is it right?
But then there is another question, If it is about the size of input, Then size of for example a number, will be unlimited. then there is worst case after worst case.Then we can not say this is the worst case, because there is another worst case too.
Pat Farrell wrote:Worse, some algorithms are exponential, something like O(2^2) they get insane fast.
SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6
How To Ask Questions How To Answer Questions
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
k=0;
for(i=0; i<n; i++)
k++;
k=0;
for(j=0; j><n; j++)
k++;
Sequential for loops are not related and loop independently of each other. The first loop will execute
n times. The second loop will execute n times after the first loop finished executing. The worst case
timing will be:
O(n) + O(n) = 2 * O(n) = O(n)
We drop the constant because constants represent 1 time unit. The worst case timing is O(n).
In this situation we calculate the worst case timing using both loops. For every i loop and for start of
the inner loop j will be n-1 , n-2, n-3…
O(1) + O(2) + O(3) + O(4) + ......
which is the binomial series:
n ( n - 1) n^2 - n n^2
------------ = ----------- = ------ = O(n2)
2 2 2
May you explain more about this:
O(n) + O(n) = 2 * O(n) = O(n)
8. power loops: O(2n)
k = 0;
for(i=1; i<=n; i=i*2)
for(j=1; j<=i; j++)
k++;
To calculate worst case timing we need to combine the results of both loops. For every iteration of
the loop counter i will multiply by 2. The values for j will be 1, 2, 4, 8, 16 and k will be the sum of
these numbers 31 which is 2n- 1.
In this situation we calculate the worst case timing using both loops. For every i loop and for start of
the inner loop j will be n-1 , n-2, n-3…
O(1) + O(2) + O(3) + O(4) + ......
which is the binomial series:
n ( n - 1)
------------ =
2
n^2 - n
----------- =
2
n^2
------ = O(n^2)
2
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |