Computer Science
posted by Elizabeth .
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)?

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

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^{n}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^{10}1 in 10 steps, i.e. up to k=n.
Since 1024 is equal to 2^{10}, therefore log_{2}(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 BigO 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.
Respond to this Question
Similar Questions

science
An area in your state has been flooded due to heavy rains. How might scientists from the three main branches of science interact in their study of the flood, its effects, and how future flooding might be controlled? 
SCIENCE
CAN SOM1 PLEZ HELP ME????? IM RUNNING OUT OF TIME 2 B ON THE COMPUTER!!!!! 
computer science
ineed help with c++. i am using code blocks and i have a problem with the compiler. when I run this code ¡é # include <iostream> using namespace std; int main() { cout<<"Hello World!"<<endl return(0); } this message … 
English
Let's write down what you can do with the computer. 1. I use the computer to chat with netizens in chatrooms. 2. I use the computer to do paper work. 3. I use the computer to make documents with the word processor, Excel. 4. I use … 
probability
out of 250 students interviewed at a community college, 90 were taking mathematics but not computer science, 160 were taking mathematics, and 50 were taking neither mathematics nor computer science. Find the probability that a student … 
computer
What does tenure track, part time instructor of computer science does? 
Child Care
Which of the following statements about children and computers is incorrect? 
computer Science
18 You started your new job as a PC tech and are at a customerâ€™s house. The computer has failed to boot. The fan is running but the POST fails every time. What is the best thing to do to possibly find quickly? 
Science
Which most resembles a scientific model? A) computer keyboard B) computer hardware C) computer game D) computer mouse 
Computer science
What is the smallest value of n such that an algorithm whose running time is (2^15)n runs faster than an algorithm whose running time is 2^n on the same machine?