Explore BrainMass

C++ big O notation

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

What does "n" represent in relation to big O notation? In other words, what does it mean? Like in O(n). I need a definition of what n is in words.

© BrainMass Inc. brainmass.com October 25, 2018, 9:00 am ad1c9bdddf

Solution Preview

Big O notation is used throughout computer science to show how algorithms behave as their inputs grow larger. It is not specific to C++; it is useful in all programming languages and in theoretical computer science.

The idea is to summarize how many steps an algorithm takes to run. But instead of just saying a number like 1,000, big O notation gives the answer as a function, for example O(n^2). Here, "n" is the size of the input to the algorithm and the algorithm takes approximately n^2 steps to run. This is much more useful than just having a single data point, such as "when the input has size 30, the algorithm takes 900 steps to run." We'd much rather have a function giving the number steps of running time for every possible input size.

For example, take ...

Solution Summary

The solution discusses and defines what the "n" represents in relation to the big O notation.

See Also This Related BrainMass Solution

Programming Essentials

1. Computer programmers often refer to memory addresses using ____
notation, or base 16.
a. binary
b. indirect
c. mathematical
d. hexadecimal

2. After a programmer plans the logic of a program, she will next ____.
a. understand the problem
b. test the program
c. translate the program
d. code the program

3. The process of walking through a program's logic on paper before
you actually write the program is called ____.
a. desk-checking
b. flowcharting
c. pseudocoding
d. testing

4. What is the problem with the following statement?
a. 100 is not a reasonable grade
b. 100 should be in quotes
c. data types don't match
d. value on the left must be a variable name

5. What might be considered the seventh step of the programming
a. testing
b. maintaining
c. replacing
d. converting

6. What symbol is used to represent output in a flowchart?
a. square
b. circle
c. parallelogram
d. triangle

7. What is the standard terminal symbol for a flowchart?
a. circle
b. lozenge
c. diamond
d. square

8. A variable name is also called a(n) ____.
a. placeholder
b. identifier
c. constant
d. hexadecimal

9. What is the assignment operator?
a. =
b. *
c. ^
d. %

10. What is an example of a string constant?
a. 1
b. 12432
c. "oops"
d. o

11. In some programming languages, programmers must write a
variable ____ telling the compiler what data type is expected for the
a. name
b. termination
c. decision
d. declaration

12. The following pseudocode is an example of a(n) ____ structure:
get number
while number is positive
add to sum
get number
a. sequence
b. decision
c. loop
d. nested

13. The following pseudocode is an example of a(n) ____ structure:
get number
get another number
if first number is bigger than second then
print first number
print second number
a. sequence
b. decision
c. loop
d. nested

14. The following pseudocode is an example of a(n) ____ structure:
get number
get another number
add numbers
print result
a. sequence
b. decision
c. loop
d. nested

15. The following pseudocode is an example of ____.
do stepA
do stepB
if conditionC is true then
do stepD
do stepE
while conditionF is true
do stepG
a. nesting
b. stacking
c. posttest
d. pretest

16. The following pseudocode is an example of ____.
if conditionA is true then
do stepE
do stepB
do stepC
do stepD
a. nesting
b. stacking
c. posttest
d. pretest

17. If a program will read 100 data records, you read the first data
record in a statement that is separate from the other 99. This is
called a ____ read.
a. nested
b. stacked
c. posttest
d. priming

18. The following pseudocode reads a number from the user, multiplies
it by 2, and prints the result. What program statement should
replace the ? to make this program functional and structured?
get inputNumber
while not eof
calculatedAnswer = inputNumber * 2
print calculatedAnswer
a. no statement is needed
b. if done then exit
c. get inputNumber
d. print inputNumber

19. Structured programs can be easily broken down into routines or
____ that can be assigned to any number of programmers.
a. segments
b. modules
c. units
d. sequences

20. One way to straighten out a flowchart segment that isn't structured
is to use what you can call the "____" method.
a. spaghetti code
b. spaghetti bowl
c. restructuring
d. priming

21. What is considered to be a convenience structure?
a. if-then-else
b. while
c. do while
d. sequence

22. The following pseudocode might be re-written using a(n) ____
if class = "Freshman" then
tuitionFee = 75
if class = "Sophomore" then
tuitionFee = 50
if class = "Junior" then
tuitionFee = 30
tuitionFee = 10
a. if-then-else
b. case
c. while
d. do while

23. In a case structure, the term ____ means "if none of the other cases
were true."
a. else
b. then
c. default
d. loop

24. In a ____ loop, the loop body continues to execute as long as the
answer to the controlling question is yes, or true.
a. do-then
b. do-when
c. do-until
d. do-while

25. In a(n) ____ loop, the loop body continues to execute as long as the
answer to the controlling question is no, or false.
a. do-until
b. do-while
c. while
d. if-then-else

26. Fill in the blank in the following pseudocode:
if someCondition is true then
do oneProcess _____ do theOtherProcess
a. then
b. while
c. do
d. else

27. What is another name for a loop structure?
a. execution
b. selection
c. iteration
d. case

28. A case structure can be replaced by one or more ____ structures.
a. if-then-else
b. do-while
c. do-until
d. while

29. Which name is best suited to a module that calculates overtime pay?
a. calcO()
b. cO()
c. calculate overtime()
d. calculateOvertime()

30. Which statement is used to indicate the end of a module?
a. stop
b. end
c. return
d. done

31. The ____ can be a useful tool when a program must be modified
months or years after the original writing.
a. flowchart
b. hierarchy chart
c. pseudocode
d. variable declaration

32. Which documentation is typically written first?
a. input
b. output
c. internal program
d. external program

33. You can design a printed report on a ____.
a. printer layout
b. print performance chart
c. print character layout
d. printer spacing chart

34. In a ____ program, the user sees a screen and can typically make
selections using a mouse or other pointing device.
a. reusable
b. modular
c. GUI
d. command-line

35. User documentation might include ____.
a. how to prepare input for the program
b. to whom the output should be distributed
c. how frequently the program needs to run
d. all of the above

36. Which step occurs first?
a. understanding user's needs
b. clarifying requirements
c. coding program
d. developing program logic

37. Checking that required input files are present would most likely
occur in the ____ section of a program.
a. main loop
b. end-of-job routine
c. housekeeping
d. file opening

38. Variable declarations are made in the ____ section of a program.
a. main loop
b. end-of-job routine
c. housekeeping
d. file opening

39. Declaring a variable involves selecting a name and a ____.
a. size
b. length
c. style
d. type

40. Some use a variable-naming convention called ____ notation, in
which a variable's data type or other information is stored as part of
the name. For example, a numeric field might always start with the
prefix num.
a. Prefix
b. American
c. Polish
d. Hungarian

41. A group of variables is often called a ____.
a. linked group
b. data structure
c. data object
d. module

42. When a variable is ____ it is both declared and initialized.
a. set
b. instantiated
c. defined
d. documented

43. How do you physically advance printer paper to the top of a page?
a. issue the pageTop() command
b. issue the top() command
c. it depends on the programming language
d. there is no way to do it

44. What is the default standard output device?
a. printer
b. monitor
c. keyboard
d. mouse

45. What is the problem with the following pseudocode if you assume
that the housekeeping() module does not perform a read?
perform housekeeping() (without read)
while not eof
read invRecord
profit = invPrice - invCost
print invItemName, invPrice, invCost, profit
a. there is no priming read and the while not eof check may fail
b. there is no check for the end of the file
c. the loop is not structured
d. there is no input

46. What is a legal statement assigning a value to the profit variable?
a. invPrice - invCost = profit
b. set profit to Subtract(invPrice, invCost)
c. profit = invPrice - invCost
d. subtract invPrice from invCost, set profit

47. Calculated values should be stored in ____ variables if they will be
used again in the program.
a. unnamed
b. temporary
c. work
d. default

48. Where is the best place to close input and output files?
a. main loop
b. housekeeping module
c. end-of-job routine
d. clean up segment

49. In a large program, a programmer might store modules in individual
files and use an instruction to ____ them in any program that uses
a. source
b. redirect
c. set
d. include

50. Which of the following would most likely be a named constant?
a. x
b. isFinished
c. taxRate

View Full Posting Details