Homework Help: Computer Science

Posted by Elizabeth on Monday, October 12, 2009 at 1:32pm.

I am learning in my computer science class about algorithms. My teacher wrote on the board:

n= 1 running time= 1
3 1+1= 2
7 1+2= 3
15 1+3= 4
31 1+4=5
63 1+5= 6
127 7
255 8
511 9
1023 10

How in the world does this happen?

It has something to do with log n steps. I don't understand this concept.

What does it mean log n= <<n for large n?

Also, what is O(n)?

Computer Science - Elizabeth, Monday, October 12, 2009 at 1:33pm
Running time is 1,2,3,4,5,6,7,8,9,10. It sll got put together, but really those numbers are separate from the n numbers
Computer Science - MathMate, Monday, October 12, 2009 at 2:15pm
Sorry to be nagging, but next time, when the teacher writes something on the board that you do not understand, raise your hand and ask for explanation. There may be 6 other students who don't understand and they would thank you for asking.

Back to the board.
If you have to calculate X=2ⁿ-1, where n=10, you can start with k=1, n=2¹-1=1
for k=2, you double the previous x and add 1 to get 3. For k=3, again double the previous x(=3) and add 1 to get 7.
If you do this 10 times, you will get 2¹⁰-1 in 10 steps, i.e. up to k=n.
Since 1024 is equal to 2¹⁰, therefore log₂(1024)=10.
The 'cost' of doing this calculation is therefore proportional to n, or approximate equal to n, or order n, or O(n).
For an explanation of the Big-O notation, you can read up:
http://en.wikipedia.org/wiki/Big_O_notation

I do not know if algebra is a prerequisite for this algorithm course, but definitely you will need to know quite well logarithms (to the base 2 and base e). Textbooks usually start off with a thorough revision of math required.

The idea behind all this is to be able to compare the efficiency of different algorithms, or way of calculating or evaluating formulas. An algorithm of O(log n) performs better that of O(n), which in turn performs better than that of O(n²), etc. This is the object of the very interesting course.

Answer this Question

Related Questions

probability - out of 250 students interviewed at a community college, 90 were ...
computer - What does tenure track, part time instructor of computer science does...
SCIENCE - CAN SOM1 PLEZ HELP ME????? IM RUNNING OUT OF TIME 2 B ON THE COMPUTER...
science - An area in your state has been flooded due to heavy rains. How might ...
CSC 111 Intruduction to Computer Science - What does it imply to pursue a ...
English - Let's write down what you can do with the computer. 1. I use the ...
math - Thomas is playing Tic-Tac-Toe with a computer. It is the computer's ...
math - Thomas is playing Tic-Tac-Toe with a computer. It is the computer's ...
computer - How does a computer generated animation work? (Points: 5) The ...
computer science - write a program to select the classes that you are taking(Ex...

For Further Reading

First Name:
School Subject:
Answer: