I was having problem with the following question

Consider the following nested loop construct. Categorize its efficiency in terms of the variable n using "big-o" notation. Suppose the statements represented by the ellipsis (...) require four main memory accesses (each requiring one microsecond) and two disk file accesses (each requiring one millisecond). Express in milliseconds the amount of time this construct would require to execute if n were 1000.

```
x = 1;
do
{
y = n;
while (y > 0)
{
...
y--;
}
x *= 2;
} while (x < n*n);
```

Inner loop with y is O(n).

Outer loop runs with x = 1, 2, 2^2, 2^3, ... 2^k < n * n. Hence it runs in O(log(n*n)) which is O(2 * log(n))

Hence complexity is O(n * log(n))

Just to add some more explanation to theother answer, a notable part of code is the x *= 2; ie a doubling. So this part is not linear. So you should be thinking log2.

Therefore, x will reach n*n in log2(n*n). = log2(n^2) = 2 x log2(n).

The y countdown is linear - so that is O(n)

There is a loop within a loop so you multiply both operations as in:

n * 2 x log2(n) = O(n * 2 * log2(n)). Then you take out constant factors to get: O(n * log2(n))

Similar Questions

It seems like none of the algorithm textbooks mentions about space efficiency as much, so I don't really understand when I encounter questions asking for an algorithm that requires only constant memor

What is the difference between Big-O notation (O(n)) and Little-O notation (o(n))?

I came upon a notation I'm not too familiar with and would like some direction to where to look. the notation is selector event : function() {} so for example .elementClass change : function() {}

When one byte is represented by 8 bits in binary notation you have a sequence of 8 possible 1's and 0's. So 00101010 can be shortened to 2A using hexadecimal notation. My book says you can shorten tha

I can't see to find an answer for this, but it's been bugging me for a while. When using multidimensional arrays in php (or any language for that matter), do you get any efficiency and productivity

I am having issues fully understanding how to prove some of the following statements. For instance I have a statement: n^2logn = O(n^2). Correct me if I am wrong, but this states that n^2 is bigO of n

I am doing exercise in Think in Python, using Memo to calculate Fibonacci sequence is far more efficiency than not using one. But when implemented it and testing the time consumed, I find the running

In a PHP file, I'm trying to convert all array notation into object notation. In other words, I'm trying to convert all occurrences of this: $thing['key'] into: $thing->key I thought this was a sim

I am finding myself concatenating QLinkedLists a lot, so I am getting concerned about the efficiency of Qt's QLinkedList::operator+( const QLinkedList<T> &other ) const I tried to look up th

I am using Enterprise Architect (version 10.0) and would like to see crow's feet notation in my ER model. so I have changed the setting to 'Information Engineering' then the notation is diappeared. No

I've tried to read SLS, but it has some strange BNF-like notation. Can any one clarify this notation. For example the Types chapter has the following: Type ::= FunctionArgTypes ‘=>’ Type | InfixTyp

Looking into Kohana documentation, i found this really usefull function that they use to get values from a multidimensional array using a dot notation, for example: $foo = array('bar' => array('col

I've been told that the following code has an efficiency O(1): void mystack::Pop_element() { assert ( nelem > 0 ); nelem--; if ( nelem < reserved / 4 ){ Resize ( reserved / 2 ); } } But I don't

How can I convert this query into dot notation var x = from Prods n in Cat.Prod.GetAllProds() orderby n.Name select new { Name = n.Name, Cost = n.Cost };

I am reading the on-line TCL command document, it uses things like ?argument?, ... and some font to designate some specific meaning, it is not hard to understand the notation, but I like to find the e

I'm currently studying and trying to implement some algorithms. I'm trying to understand Big O notation and I can't figure out the Big O complexity for the algorithm below: while (a != 0 && b

What are the right situations to use %w: percent_notation = %w(first second third) explicit = [first, second, third] for creation of arrays? With arrays of size 501, the difference in creation

I am try to understand this code: Var1 = re.compile(rnothing is (\d+)).search i am want to see what is the affect of the r notation right after the ( sign on the \d. i know that \d mean to find dec

While perusing an application that I'm documenting, I've run across some examples of bang notation in accessing object properties/methods, etc. and in other places they use dot notation for what seems

I am experimenting with syntax mods in Mathematica, using the Notation package. I am not interested in mathematical notation for a specific field, but general purpose syntax modifications and extensio

I need a formula that will determine the efficiency of the system in pattern matching using time and the number of comparison factors. Is there any formula that would produce numeric output using thes

i am trying to find limitations of o notations, i was wondering if there was a simple example that demonstrates an enahncement to a task, where version 1 is the same o notation as version 2, yet versi

I'm a bit confused as to why NumberStyles.AllowExponent alone does not parse my decimal in scientific notation. This throws an exception: Decimal.Parse(4.06396113432292E-08, System.Globalization.Num

If you submit an update statement to a RDBMS in which the order of the column_name = value mappings don't match the physical layout of the file, does it affect (theoretically) the efficiency of the up

I know that there is so many standards for writing code. and some policy tools (like FxCop) to check your writing statements. What's the best hungarian notation or any other snippets for writing codes

I've made some researches but I didn't find a good article. I am adding multiple Vectors to one Vector, after that I am printing it: Iterator it =vector.iterator(); while(it.hasNext()){ System.out.pri

I was just remembering back my university classes and was wondering to know if anyone out here even used the Z notation in a professional environment. I honestly must say that it was the single most

Recently,I'm working on a gevent demo and I try to compare the efficiency between gevent and thread. Generally speaking，the gevent code should be more efficient than the thread code. But when I use ti

I wonder what is the efficiency of the following snippet: val lst = Source.fromFile(f).getLines.toList When issuing lst.contains(x), does it mean that f is being re-scanned, or is it the case that t

I've been doing some questions but answers not provided so I was wondering if my answers are correct a) given that a[i....j] is an integer array with n elements and x is an integer int front, back; wh

I was just reading an answer to a different question on nsxmlparsing.. and in it the guy was saying you should use self. notation for better memory management... what dose this mean? I have left this

In javascript, properties of objects can be accessed using dot-notation instead of bracket-notation -- object.propertyName can be used in place of object[propertyName]. How can I do this in C#? As a

Hello I am trying to get the efficiency for Strassen's algorithm but need some help. The recurrence relation for the algorithm is the following: A(n) = 7A(n/2)+18(n/2)^2, for n>1, A(1) = 0. I've s

I am studying up for a pretty important interview tomorrow and there is one thing that I have a great deal of trouble with: Sorting algorithms and BigO efficiencies. What number is important to know?

Is there any way to convert scientific notation to fixed notation in Java. Currently I have got the following code: DecimalFormat dfmt=new DecimalFormat(######:#######); print(dfmt.format((new BigDe

I'm working through Write yourself a scheme interpreter in 48 hours and one exercise is to write a function using do notation. This is the function: parseNumber :: Parser LispVal parseNumber = liftM

I'm playing with some piece of code calculating the time needed to compute some Java code to get a feeling of the efficiency or inefficiency of some of Java's functionality. Doing so I'm stuck now wit

The question is &str[2], if I write str+2 then it would give the address and its logical but where did I used pointer notation in it? Should I prefer writing &(*(str+2))?

What Big-O notation questions have you been asked? Did you find them to be good questions? Did the interviewer actually understand the concept?

When i make the following multiplication in PHP: $ret = 1.0 * 0.000000001; i get the result: 1.0E-9 I want to convert this result into the normal decimal notation, how can i do this? sprintf('%f',$re

Background Information Ordinal position notation, AKA ordinals, is column shorthand based on the column order in the list of columns in the SELECT clause, instead of either the column name or column a

I'm looking for a commonly understandable notation to define a fixed point number representation. The notation should be able to define both a power-of-two factor (using fractional bits) and a generic

I've come across some code which could definitely be improved, but i'm wondering about the Big-O notation of my improvements. Their original code adds a element to an array, and each time it does this

I've started to learn a new PHP notation I like better than the standard <?php if (...) { // code here } ?> Instead, it uses <?php if (...) : // code here endif; ?> But I can't figure o

Is there a big difference in efficiency when using Point2D instead of double x and y values? I'm working on a program that has many circles moving around the screen. They each start at one point, and

Is it possible to log numbers in binary notation? For example Logbinary(0x3) should give my 0111 when using signed notation.

I can't find an utility or a more complete software that can translate rows of text i write in BNF into diagrams with vector formats like svg, someone can help me with this?

Is there a way to make this call in dot notation?: [someSwitch setOn:YES animated:YES]

I have an efficiency-based question regarding LINQ vs a standard foreach loop. I have a method, which does approximately the following var foos = users.Select(this.GenerateNullableFoo).Where(foo =>

Is there any code out there (or a built-in function) which allows outputting a floating point number in engineering notation? For example, 1.5e-4 would be displayed as 150µ and 5e-3 would be displayed