big-o,computer-science , Would this function be O(n^2log_2(n))?


Would this function be O(n^2log_2(n))?

Question:

Tag: big-o,computer-science

So I am given a function like 65536 n2 + 128 n log2n

and the only way that this would be O(n2 log2n) is if

C = 65664, n0 = 2 for all n ≥ 2 since

C1 = 65536 n1 = 2 when 65536 ≤ C1*n2 and
C2 = 128 n2 = 1 when 128 ≤ C2*n

but the number I've chosen for the constant seems a bit to high, is there a way to check this?


Answer:

O(65536 n2 + 128 n log2n) is the same as O(n2 + n log2n) since you can ignore multiplicative constants. O(n2 + n log2n) is equal to O(n2) since n2 grows faster than n log2n.

Also, by the way, the base of logarithms doesn't matter in Big-O analysis. All logarithms grow at the same rate. After all, log2n = log n / log 2, and multiplicative constants can be factored out. You can simply say log n instead of log2n.

Caveat: Technically, it is actually a true statement to say that 65536 n2 + 128 n log2n ∈ O(n2 log2n) because Big-O gives an upper bound, but not a strict one. O(n2) is a lower upper bound, if that makes sense.

That said, you should not have come up with O(n2 log2n). That was merely the result of accidentally turning an addition into a multiplication. As a rule of thumb, if you have multiple things added together inside a Big-O formula, you just have to figure out which one of them grows the fastest and then discard the others.


Related:


Why is `nil` discussed as boolean by treehouse?


ruby,boolean,computer-science
Why is nil considered a boolean or represented as a boolean value in the boolean tutorial for ruby? By definition, a boolean in computer science is a: data type, having two values (usually denoted true and false), intended to represent the truth values of logic and Boolean algebra. ...

I'm timing a function that has a runtime of O(n^3) but my timing results do not show this, why is this happening?


matlab,big-o,time-complexity
numberOfTrials = 10; numberOfSizes = 6; sizesArray = zeros(numberOfSizes, 1); randomMAveragesArray = zeros(numberOfSizes, 1); for i=1:numberOfSizes N = 2^i; %x=rand(N,1); randomMTimesArray = zeros(numberOfTrials, 1); for j=1:numberOfTrials tic; for k=1:N^3 x = .323452345e-999 * .98989898989889e-953; end randomMTimesArray(j) = toc; end sizesArray(i) = N; end randomMPolyfit = polyfit(log10(sizesArray), log10(randomMAveragesArray), 1); randomMSlope =...

Big-O for 2 dimensional array and Linked list


c++,c,arrays,linked-list,big-o
I've made a game by using 9 linked Lists and the other 1 linked lists gets all the address of the other 9 linked lists. Therefore, something like a 2 dimensional array by using linked list. I'm trying to calculate Big-O that my data structure fits and is better than...

Have I properly sorted these runtimes in order of growth?


math,big-o,time-complexity,asymptotic-complexity
I am doing this small task which I have to arrange asymptotic runtime in ascending order. Here are the runtimes: Here is the order I believe they should go in: log10(n^4), n^3, 2^((log4n)), 2^(100n), e^pi^4096, n! + 12^1000 Is this correct? Or are there any errors? Thanks!...

Compare growth of function


algorithm,big-o
I have the following: n! nlogn 2 ^ n sqrt3(n) = n^1/3 n ^ 3 We know that in order to compare two functions we need lim n->infinity f(n) / g(n) But we also know that exponential > polynomial > polylogarithmic. We also know from stirling that n! = o(n^n)...

Performance Improvement Basics in Python


python,algorithm,performance,big-o
So this is an algorithms question I was working out on HackerRank. It passes all the test cases except one because it times out. I tried making a couple of improvements but it still keeps timing out. I want to understand how you can look at your own code and...

Why is the cost of a hash lookup O(1) when evaluating the hash function might take more time than that?


hash,hashtable,big-o,time-complexity
A HashMap (or) HashTable is an example of keyed array. Here, the indices are user-defined keys rather than the usual index number. For example, arr["first"]=99 is an example of a hashmap where theb key is first and the value is 99. Since keys are used, a hashing function is required...

How to find out time complexity of mergesort implementation?


algorithm,big-o,time-complexity
We all know that merge sorting algorithm time complexity is "N Log N". But from this below code how to calculate this "N Log N" big O notation step by step ? There are some answer about this question on internet but they are very complicated to understand. Please help...

Big O notation for the complexity function of the fourth root of n


algorithm,math,big-o,time-complexity,complexity-theory
I am expected to find the Big O notation for the following complexity function: f(n) = n^(1/4). I have come up with a few possible answers. The more accurate answer would seem to be O(n^1/4). However, since it contains a root, it isn't a polynomial, and I've never seen this...

Brick-Breaker in C - incrementing rows of bricks issue


c,function,for-loop,computer-science
I'm trying to re-create brickbreaker using C and the Stanford Portable Library (SPL). The goal of my initBricks function is to add 5 ROWS of bricks with 10 COLUMNS in each row (50 bricks total). When I run this code my window only has 1 ROW of 10 bricks. For...

Exponential growth doubling processor speed


algorithm,big-o,complexity-theory,exponential
According to Wikipedia article on Exponential growth E.g. if a slow processor can solve problems of size x in time t, then a processor twice as fast could only solve problems of size x+constant in the same time t. My question is, how do we calculate the constant value that...

What is the Time Complexity of finding the max k integers?


python,algorithm,dictionary,big-o,time-complexity
def max_k_sort(k, nums): # sort nums first using timsort # add O(n*log(n)) time complexity sorted_nums = sorted(nums) return sorted_nums[-1*k:len(nums)] def max_k(k, nums): # build initial max number list max_nums = {} # add O(k) time complexity? i = 0 while i < k: max_nums[i] = 0 i += 1 #...

Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)


algorithm,recursion,big-o,complexity-theory,recurrence
The question comes from Introduction to Algorithms 3rd Edition, P63, Problem 3-6, where it's introduced as Iterated functions. I rewrite it as follows: int T(int n){ for(int count = 0; n > 2 ; ++count) { n = n/log₂(n); } return count; } Then give as tight a bound as...

Would this algorithm run in O(n)?


algorithm,big-o,time-complexity,complexity-theory,asymptotic-complexity
Note: This is problem 4.3 from Cracking the Coding Interview 5th Edition Problem:Given a sorted(increasing order) array, write an algorithm to create a binary search tree with minimal height Here is my algorithm, written in Java to do this problem public static IntTreeNode createBST(int[] array) { return createBST(array, 0, array.length-1);...

Would this function be O(n^2log_2(n))?


big-o,computer-science
So I am given a function like 65536 n2 + 128 n log2n and the only way that this would be O(n2 log2n) is if C = 65664, n0 = 2 for all n ≥ 2 since C1 = 65536 n1 = 2 when 65536 ≤ C1*n2 and C2 =...

Computer architecture - How to find the addresses in a block


computer-science,computer-architecture
A cache memory with 4 KiB, each block is 16 words, there are 64 lines in the cache. Tag = 18 Index = 6 Block offset = 4 Byte Offset = 2 I want to know for block number 448 what is the first address in the block and what...

time complexity analysis for finding the maximum element


algorithm,big-o,time-complexity,lower-bound
I've encountered a homework problem. which of these is an asymptotically tight upper bound for the best-case running time of an optimal algorithm that finds the maximum element in an arbitrary array of integers of size n (1) O(logn) (2) O(n^2) (3) O(n) (4) O(1) (5) O(nlog(n)) Based on my...

Understanding Big-Ω (Big-Omega) notation


algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

Ternary vs Chained If-else-if (Performance)


c#,performance,if-statement,big-o,ternary
I did the due-diligence to see if this has been asked before and didn't find anything identical but close, so here goes. Say I have a chain of if-else-if statements. foreach (value in valueList) if (value == 120) { w = true; } else if (value == 140) { x...

Big-O Computational Resources


algorithm,sorting,big-o,computer-science,asymptotic-complexity
I know that measuring asymptotic complexity can be based on any resources you have, whether it's time, memory usage, number of comparisons, etc. But when it comes to sorting something, I realize we normally associate the asymptotic notation with the basic operations like number of swaps/steps or number of comparisons....

Big O Notation with Absolute Value?


graph,big-o,notation
I'm going through some programming interview question books, and I've seen reference to "O(|A|)" time complexity. I've never seen this notation with the absolute value given. Some research led me to Big O Cheatsheet that references this notation under the graphs section. The problem I'm researching is about partitioning an...

Intro to Algorithms (chapter 1-1)


algorithm,big-o
Just reading this book for fun, this isn't homework. However I am already confused on the first main assignment: 1-1 Comparison of running times For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t,...

Update minimum spanning tree if edge is added


algorithm,graph,tree,runtime,big-o
I have a possible solution for the following question, but not sure if correct: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is...

Big O Nested for Loop issue


java,big-o
public static void main(String[] args) { int count = 0; int n = 20; for (int i = 0; i < n; i++) { for (int j = i; j > 0; j--) { count++; } } System.out.println(count); } Above is the code of a simple nested for loop...

What part of my code is making my performance suffer? (Codility's MaxCounter)


java,algorithm,data-structures,big-o,time-complexity
I have the following problem: You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty zero-indexed array A of...

Best algorithm to find N unique random numbers in VERY large array


performance,algorithm,big-o,bigdata,asymptotic-complexity
I have an array with, for example, 1000000000000 of elements (integers). What is the best approach to pick, for example, only 3 random and unique elements from this array? Elements must be unique in whole array, not in list of N (3 in my example) elements. I read about Reservoir...

TIme complexity of various nested for loops


loops,for-loop,big-o,time-complexity,asymptotic-complexity
Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount. loop 1 ---- for (int i = 1; i <=n; i *= c) { // some O(1) expressions } loop 2 ----- for (int i = n; i >...

Big-O insert for 2 dimensional array


c++,c,arrays,big-o
If i have N x N 2 dimensional array and the name is a. int a[N][N]; When i Insert any value in any array, for example, a[N-1][N-1]=1, how much time does it take? O(N^2) or O(1)?...

Solving a complex recurrence relation for the Traveling Salesman


algorithm,math,time-complexity,computer-science,recurrence-relation
I need to solve the exact time complexity for the brute force version of the Traveling Salesman using a recurrence relation. I've worked out the recurrence relation to be as follows: T(n)=T(n-1)*(n-1)+1 But I'm having trouble reducing that that to a closed form of the function, and thus get the...

Determining the Big O complexity for “for” loops.


big-o,time-complexity
I have 3 for problems I having trouble determing the Big O complexity for. A. int x = 0; for ( int y = 1; y <= n * n; y++) for ( int z = 1; z < y; z++ ) x++; I want to say n3 because the...

What is the big-O complexity of this code


big-o,time-complexity
Whats the big-O notation of this code? for( int i=1; i<2n; i++) x=x+1; My answer = O(2*n) Is this correct?...

Can Fibonacci Heap have more than one nodes with equal rank(or value, or key)?


algorithm,heap,computer-science,fibonacci-heap
I am studying Fibonacci heap alone, and I came across a question. I know any nodes can be inserted into Fibonacci heap, but what if the rank(or value, or key) of that new node is equal to the sibling node? 1) For example, (1) <-minimum root / \ (3) (5)...

Keyboard events java


java,computer-science,keylistener,keyevent
I have recently started learning java.I want to make a game like https://sites.google.com/site/millseagles/home/Games/multiplayer/tron I have made it in c++ once using a simple graphics lib. I have the graphics part down i plan to use small images and use http://horstmann.com/sjsu/graphics/ this basic graphics lib.I can't figure out keyboard input i...

is this the most efficient way?


java,arrays,big-o
I'm looking for the greatest difference between 2 doubles in a list, I have done it this way in NlogN time, is there a way to do it in linear time? thanks! public static double NlogN(double[] ar){ Arrays.sort(ar); double max=ar[ar.length-1]; double min=ar[0]; double difference=max-min; return difference; } ...

What is the Big-O complexity of this code?


big-o,time-complexity
What would be the big O for void fun(int n) { for(i=1; i<=n; i=i+2) { } } My answer: O(log n) (since the i values is 1,3,5,7,9 reducing by 2 overall) void fun(int n) { for(i=1; i<=n; i=i+2) { } } My answer: O(log n), since this is quadratic (i...

Sum of all subparts of an array of integers


arrays,algorithm,sum,big-o,subset
Given an array {1,3,5,7}, its subparts are defined as {1357,135,137,157,357,13,15,17,35,37,57,1,3,5,7}. I have to find the sum of all these numbers in the new array. In this case sum comes out to be 2333. Please help me find a solution in O(n). My O(n^2) solution times out. link to the problem...

Update minimum spanning tree if edge is removed


algorithm,graph,tree,runtime,big-o
I am having trouble with the following question: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is removed from G to produce a...

find element in linked list


algorithm,linked-list,computer-science
There is a data structure providing iterators with the following interface: struct iterator { T value(); void next(); bool isValid(); } How would you design an algorithm which at the end of the loop returns some value from the list with equal probability for each element? The list can be...

What is better BigO log(m*n) or (m+n)?


algorithm,big-o
With m and n being the two dimensions of a 2D matrix, which search algorithms with givens Big-O are considered faster: log(m*n) or (m+n) or log(m)*log(n)? ...

Is the execution time of this unique string function reduced from the naive O(n^2) approach?


c++,c,algorithm,big-o
The generic algorithm to deduce if a string contains all unique characters (and that does not use any other data structures) says to go through the string, iterating each letter against the entire string searching for a match. This approach is O(n^2). The approach below (written in C) uses an...

How do people create new programming languages?


c,programming-languages,computer-science,systems-programming,inventions
I'm novice programmer, learning C. Something that's always confused me is how do people create new programming languages? Sub/related questions: What language do they write it in? Does the language have to be one that in between a high level language and machine code? What are the stages/elements of creating...

Need workaround to treat float values as tuples when updating “list” of float values


python-2.7,matplotlib,computer-science,floating-point-conversion
I am finding errors with the last line of the for loop where I am trying to update the curve value to a list containing the curve value iterations. I get errors like "can only concatenate tuple (not "float) to tuple" and "tuple object has no attribute 'append'". Does anyone...

What is the term used to describe a complete call frame cycle thing in JavaScript?


javascript,computer-science
In JavaScript, there is the concept of the execution pathway beginning at a certain point (such as an event handler), with the control being relinquished back to the browser at some point. Is there a proper name for this process? Originally I thought you could refer to this as the...

How can I tell how many times these nested statements will execute?


algorithm,sorting,big-o,time-complexity,complexity-theory
I have the following pseudocode: SelectionSort(A) n = A.length for j=1 to n-1 smallest = j for i=(j+1) to n if A[i] < A[smallest] smallest = i exchange A[j] with A[smallest] I think that the first for-loop test will execute n times, and the nested for-loop will execute 1 +...

Why are my nested for loops taking so long to compute?


algorithm,matlab,time,big-o,nested-loops
I have a code that generates all of the possible combinations of 4 integers between 0 and 36. This will be 37^4 numbers = 1874161. My code is written in MATLAB: i=0; for a = 0:36 for b= 0:36 for c = 0:36 for d = 0:36 i=i+1; combination(i,:) =...

Java: 2d array - making it “torus” like


java,computer-science
I am facing following problem: I have a board of size MxN squares. What is the best way to make it in java so that when there are coordinates given which are out of bounds (or with negative values), it will return square from the other side of the board?...

How to find the Big O when there are two separate for loops


c,for-loop,big-o
I know how to find Big O for "for loops" and nested "for loops", but what happens when we have two for loops, not nested but two separate for loops in the same function.

Why is only one of the given statements about complexity classes correct? [closed]


algorithm,big-o,time-complexity,complexity-theory
Apparently the correct answer to the following question is (C), but why are the other options not correct until we know the value of n? If n=1, all of these seem correct except (B)! Where am I going wrong? Which of the following is not O(n2)? (A) 1510 * n...