I've read the topic:

Big O, how do you calculate/approximate it?

And am not sure what the Big-O notation for the following function would be:

```
static int build_nspaces_pattern(const char * const value, char *pattern,
size_t sz_pattern) {
static char val_buffer[1025];
char *ptr, *saveptr;
size_t szptrn;
ptrdiff_t offset;
val_buffer[0] = '\0';
strncat(val_buffer, value, sizeof(val_buffer) - 1);
val_buffer[sizeof(val_buffer) - 1] = '\0';
pattern[0] = '^'; pattern[1] = '('; pattern[2] = '\0';
for ( ptr=strtok_r(val_buffer, ",", &saveptr);
ptr!=NULL;
ptr=strtok_r(NULL, ",", &saveptr)
) {
szptrn = sz_pattern - strlen(pattern) - 1;
if ( sanitize(ptr) != 0 ) {
return -1;
}
strncat(pattern, ptr, szptrn);
szptrn -= strlen(ptr);
strncat(pattern, "|", szptrn);
}
offset = strlen(pattern);
pattern[offset-1] = ')'; pattern[offset] = '$'; pattern[offset+1] = '\0';
return 0;
}
```

Sanitize is O(n), but the for loop will run k times (k is the number of commas in the string).

So, k * O(n) is still O(n), would it be O(n^2), O(k.n) or something else?

Thanks.

~~Looks O(n) to me, at a glance.~~

`strtok_r()`

iterates through the original string = O(n)`sanitize()`

you say is O(n), but this is presumably with respect to*the length of the token*rather than*the length of the original string*, so multiply token length by number of tokens = O(n)`strncat()`

ends up copying all of the original string with no overlap = O(n)you append a fixed number of characters to the output string (

`^`

,`(`

,`)`

,`$`

and a couple of NULLs) = O(1)you append a

`|`

to the string per token = O(n)

**But wait!**

- you call
`strlen()`

over the output pattern*for every iteration of the loop*= O(n^2)

So there's your answer.

One way to approach it I like is to replace code with the running times, so for instance

```
val_buffer[0] = '\0';
strncat(val_buffer, value, sizeof(val_buffer) - 1);
val_buffer[sizeof(val_buffer) - 1] = '\0';
```

becomes

```
O(1)
O(n) (* Assume the size of value is the size of the input *)
O(1)
```

A loop

```
for each k in value {
strlen(value)
}
```

becomes

```
O(n) {
O(n)
}
```

or something such notation, which you can then make into `O(n) * O(n) = O(n^2)`

. You can then sum up all the listed big-oh times to obtain your final time complexity.

A similar trick is to first lace all of your code with counts of how much work is done, then remove the code that does the real work leaving only the counts. Then using simple math to simplify the counts. I.e.,

```
count = 0;
for (i = 0; i < k; i++) {
count++
}
```

is easily seen to be replaceable by `count = k`

.

Why is everyone assuming strlen = O(n)? I thought O(n) was only for loops.

Similar Questions

I have copied the following code from here and here. I want to know is exception handling required for the following code ? What hapens if an exception is thrown before the DB connection is closed, so

The sequence is: 00111011 How do i calculate the parity bit for the above sequence? This question is from Databases- The complete book by jeffery ullman (Exercise 13.4.1 a) I am not sure what the answ

How can i calculate the size of only some rows for each table? For example, with the code: EXEC sp_spaceused 'myTable' you obtain the size of all rows, however i want to calculate the size not of one

The following class just has one method that returns the divisor of a certain percent, so if I pass it 5, it will return 0.05. public class Adjustment { public decimal Amount {get;set;} public bool Is

I've experienced some problems when I try to print the data stored inside the binary tree by BFS(Breadth first search), so, here is my code: The class BTree is used only for the insertion of the data,

I know that the following do notation's bind function is equivalent to getLine >>= \line -> putStrLn do line <- getLine putStrLn line But how is the following notation equivalent to b

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 was just wondering what is the time complexity of the following code. The time complexity (Big O) of the code below in my opinion would be O(n^4) What do you guys think? int result = 0; for(int i =1

The block is: i=2 while(i<n){ i=i*i; x=x+1; } I need to find the theta notation for how many times x=x+1 executes. I created a table with some sample values but I can't figure out how to move on

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

The following code does not parse: main :: IO () main = do print $ result where result = foldl' (+) 0 [1..1000000] print $ result where result = last [1..1000000] The compiler complains on the second

How to convert the scientific Notation in to Double.. Please kindly refer the image For your reference on the header column i want to display the original - or + value i want to display not scien

I am new to jQuery. What does the following code mean? Especially the first part. $(.locale-en-us, $iframe).append($('script').attr('type', text/javascript).attr('src', https://mytestbox/testsite

I have a C#.NET application running on a machine. How do I calculate the checksum of the entire code at runtime? Note: I do not want to calculate the checksum of the image in use but the actual code p

How can I calculate the execution time in the following code: #include <stdio.h> /* Core input/output operations */ #include <stdlib.h> /* Conversions, random numbers, memory allocation, e

I defined this notation: Definition Id (n:nat):= n. Notation 'ID' { n } := (Id n) (no associativity, at level 99). Which works just fine. Now I want to add format to change the line breaks and alig

I tried to get the output for this code but I am getting error, when compiling the program and the error is illegal start of expression class Main { public static void main(String[] args) { static

I have a line of code in Joomla- horizontal and vertical are two layout options. require(JModuleHelper::getLayoutPath('mod_fwrealestate_search', ($params->get('layout') == 'horizontal')?'horiz

Test case : 35000 -> a normalized scientific notation of the number would be 3.5 * 10E4 -> the engineering notation would be 35 * 10E3 A simple algorithm that does this would keep dividing the

I have tried the following code in many ways but it just doesn't work. I have two problems with it. I need it to not continue to QUANTITY when I press X. If I want to continue, i.e., I do not press X

I am just starting to learn about Big O notation and had a question about how to calculate the growth rate of an algorithm. Suppose I had an algorithm with O(√n log n) time complexity, and for n = 10

I am really bad at math and i can't calculate the following thing.. I have two columns named experience and level . If experience is over 200 then level is updating to 1 If experience is over 500 then

This question already has an answer here: how would I go about accessing a deep value using a single variable in bracket notation? 3 answers I want to do this: market['global']['name'] Like th

I would like to write a utility class that will help me determine how much garbage a certain piece of code is making. Something I can use like this: GarbageProfiler.Start(); and int numGarbage = Garba

I know how to write a query notation join in dot notation, but how do you write a cross join in dot notation? List<Alpha> als = new List<Alpha>{new Alpha(), new Alpha()}; List<Bravo>

How can I write mathematical notation (ital, sub/sup script, greek letters) in and html page. I need this letters to be inline. I tried wrapping them with <MI></MI> or <MATH></MAT

I am lost on these code fragments and finding a hard time to find any other similar examples. //Code fragment 1 sum = 0; for(i = 0;i < n; i++) for(J=1;j<i*i;J++) for(K=0;k<j;k++) sum++; I'm

I got stack level too deep error when I add following code in my controller. What's wrong and how to fix it? PS: If I replace @survey.questions << Question.new(params{}) with Question.new(p

I am somewhat familiar with Big O notation, however I came across an explanation of Big O notation that I cant quite get. int foo(int n) { int p = 1; -------------->c1 x 1 int i = 1; -------------&

I'm working on a program where the user inputs 3 values (one of which is in dictionary notation form).. but I'm having trouble finding out how to work with this special notation. The user input will

I've read % notation but I could not find the explanation about the followings. Example 1: The following code with % outputs i. Obviously % changes i to a string. But I am not sure what actually % is

I was trying to convert this code into a more elegant or efficient way to code it. final ContentSlotForPageModel rel = modelService.create(ContentSlotForPageModel.class); rel.setUid(rel_1); rel.set

How to give SD Card File Path in following Code? String s=file:///sdcard/tempImage.png; parameters.putString(attachment,{\name\:\Android Facebook application By Martin\,\href\:\http://www

I am new to angularjs and want to do the following in angularjs way Controller $scope.Filter = function($event, active, id) { html = ; if(active){ $http({method: 'GET', url: someUrl.json}). succes

Is it possible to create Zed Notation schemes in LyX? How can it be done?

I know there are quite a bunch of questions about big O notation, I have already checked Plain english explanation of Big O , Big O, how do you calculate/approximate it?, and Big O Notation Homework--

I have the following code: public void CheckAuthorization() { string app_id = ;//Your id here string app_secret = ;//your secret key string scope = publish_stream, manage_pages; if (Request[co

I opened semicolon delimited txt file with this code below and long account number showed up as scientific notation after saving to excel regardless of formatting to text that column. What did I do wr

Im confused on how to prevent SQL injection, I've looked online. Do I use a store procedure, or do I Create variables, Im just completely lost. Try connection.Open() ’we got here so our connection t

Consider a typical environment, why is the following code illegal in C? { int x; &x = (int*) malloc(3*sizeof(int)); ... }

Can anyone explain the following PHP Code ? function get_param($param_name, $param_type = 0) { global $HTTP_POST_VARS, $HTTP_GET_VARS; $param_value = ; if (isset($_POST)) { if (isset($_POST[$param_n

I create the JSON object , in this sample circular reference error is occured. Why circular reference error is occured and how to resolve circular reference error? give the full details about this iss

I read the doc about condp from clojuredoc. And in the doc I found the following code: (condp some [1 2 3 4] #{0 6 7} :>> inc #{4 5 9} :>> dec #{1 2 3} :>> #(+ % 3)) The result of th

This question already has an answer here: Finding the total number of set-bits from 1 to n 8 answers I see a code that is used to calculate the total number of 1-bits in all integers in range(0

Possible Duplicate: Do the parentheses after the type name make a difference with new? Hi guys, I have a question about C++ regarding to the following code: Test *t1 = new Test; // there is no () af

I have the following code that works and gives me the solution that I am looking for, however what I would like to do is break out the following section into i's own class so that I can initialize the

suppose i have the following php code and i need to use the function named any_function in the string named $someotherthing, how can i use it, please help??? and also can i use the string ($something)

I have been using square bracket notation in Javascript to create and call associative arrays. In this example, I understand that square bracket notation allows you to use a variable to call a certain

Is there any math utility method to calculate the following expression? Basically, I need to find the largest integer less than or equal to x which can be divided by N evenly. x - x % N; // N is an i

I need to show one element in scientific notation. The cout is located inside few loops and after setting the scientific notation, it affects the whole cout in the program. How can I switch back to re