For the below function,

I did

But I must have did wrong ... answer should be `O(log n)`

. I am terrible at Big O ... havent fully understood master theorem which is not taught in school yet. They taught only recursion tree

If we suppose that all arithmetic operations are done in O(1) then: As we see each function call we divide exp on 2. When we reach zero with exp - we done. How many times we can divide exp on two without reaching zero? That's log exp. So the log exp function calls * O(1) gives log(exp) complexity. Finding sum of geometric sequence you finding answer to another problem: how many node in complete (where all siblings exist) tree with n leaves: suppose n = 4:

1' |_1'' |_1''' |_2''' |_2'' |_3''' |_4'''

you are finding count of node in such a tree

The assumptions you make at the beginning of your math is saying that you spend "n" time in the function call `Exp(n)`

, "n/2" time in `Exp(n/2)`

, "n/4" time in `Exp(n/4)`

and so on...

But, actually, you only spend constant `O(1)`

time in each function call. So, then you have `log(n)`

function calls of constant time. Try running the rest of your math with this starting assumption and see what you get.

Similar Questions

What is the running time of this algorithm: for i=1 to n^2 for j=1 to i // some constant time operation I want to say O(n^4) but I can't be certain. How do you figure this out?

For homework, I was given the following 8 code fragments to analyze and give a Big-Oh notation for the running time. Can anybody please tell me if I'm on the right track? //Fragment 1 for(int i = 0;

I'm smashing my head from hours trying to achieve an exponential increase. I tried with second degree equation but the result is not what i expected. Let me explain. I have a pay per use service based

In big-O notation is O((log n)^k) = O(log n), where k is some constant (e.g. the number of logarithmic for loops), true? I was told by my professor that this statement was true, however he said it wil

Possible Duplicate: Convert exponential number to decimal in php Is there a way to convert an exponential number to a whole number in PHP using built in functions? A format function? 1.2378147769392

I am working on some revision at the moment and specifically going over Big-O notation. I have asked a similar question (which dealt with a different algorithm) but am still unsure if I am going the r

Suppose f(n) is runtime of algorithm. According to function definition of O(n), if f(n)<=c*g(n) then f(n)=O(g(n)) where n0<=n. What is the range of values constant c can take?

Is big-O notation a tool to do best, worst, & average case analysis of an algorithm? Or is big-O only for worst case analysis, since it is an upper bounding function?

I've tried to come up with the Big O Running time of the following data structures. Are they Correct? Inserting n integers into an initially empty AVL Tree (best case) O(log n) Inserting n integers i

I would like to generate a random variable having an exponential density function: f(x) = e^x / (e - 1), 0 <= x <= 1 I know I can use a uniform random number generator with using the inversion m

In one discussion among colleagues I have heard that function point analysis is not used nowadays since it can go wrong for various reasons. So WBS (work breakdown structure) is used commonly. Is that

My program of sorting values clocks at: 100000 8s 1000000 82s 10000000 811s Is that O(n)?

I was given the following code and was told to find the best and worst case running times in big theta notation. def find(a, target): x = 0 y = len(a) while x < y: m = (x+y)/2 if a[m] < target:

Preparing for technical interviews, I solved a practice problem with a recursive solution. What is the runtime complexity of a recursive function such as this? I am more concerned with the explanation

What are some examples where Big-O notation[1] fails in practice? That is to say: when will the Big-O running time of algorithms predict algorithm A to be faster than algorithm B, yet in practice algo

I am trying to get a grasp on Big O notations. It seems pretty abstract. I selected the most common data structures - array, hash, linkedl list (single and double) and a binary search tree and guessed

What will be the Big O notation for the above complexity? Is it O(n)

I'm new to Big-O notation, so I need a little advice. Say I have a choice of two algorithms: one with several for loops in a row, or one with a thrice nested for loop. For example, one is structured s

I have an array of data which, when plotted, looks wave.I need to determine the best fitting (linear and exponential) for these data and find the value of lambda 1,lambda 2 and tau in this function ((

I'm having difficulty determining the big O of simple recursive methods. I can't wrap my head around what happens when a method is called multiple times. I would be more specific about my areas of con

I'm asked to give a big-O estimates for some pieces of code but I'm having a little bit of trouble int sum = 0; for (int i = 0; i < n; i = i + 2) { for (int j = 0; j < 10; j + +) sum = sum + i +

I am having a hard time proving that n^k is O(2^n) for all k. I tried taking lg2 of both sides and have k*lgn=n, but this is wrong. I am not sure how else I can prove this.

I am trying to analysis time complexity of below function. This function is used to check if a string is made of other strings. set<string> s; // s has been initialized and stores all the string

Possible Duplicate: Big Theta Notation - what exactly does big Theta represent? I understand it in theory, I guess, but what I'm having trouble grasping is the application of the three. In school, w

I have experimental data for exponential distribution a*exp(b*x). the objetive is to find the coefficients a, b and their errors. I have tried using the function fit(B,C, 'exp1') and got some results.

Is there a good reference (table or chart) out there somewhere that shows all the time and space complexity in Big-O notation, for all the common operations (add,remove,iterate,etc.) for many of the c

can anyone help me calculate the complexity of the following? I've written a strStr function for homework, and although it's not part of my homework, I want to figure out the complexity of it. basical

How can I represent the complexity of std::find_end algorithm as Big-O notation? The complexity of std::find_end is defined as follows: At most (last2 - first2) * (last1 - first1 - (last2 - first2) +

So, I really don't get Big O notation. I have been tasked with determining O value for this code segment. for (int count =1; count < n; count++) // Runs n times, so linear, or O(N) { int count2

I am new in the algorithm analysis domain. I read here in the Stack Overflow question Plain English explanation of Big O that O(2n^2) and O(100 n^2) are the same as O(n^2). I don't understand this,

I wonder whether there is any automatic way of determining (at least roughly) the Big-O time complexity of a given function? If I graphed an O(n) function vs. an O(n lg n) function I think I would be

i need help finding time complexity of this function in big O notation: int myfunction(bool exists) { int var=0; int k,j,n; if (exists) for(k=1; k<=n; k*=2) for(j=1; j<=k; j++) var++; else for(k

I've been working through a recent Computer Science homework involving recursion and big-O notation. I believe I understand this pretty well (certainly not perfectly, though!) But there is one questio

Hey i have a question. say t(n) = O(n log(n)) and u know that this is true. and then your given these statements and told to say whether they must be true or false. t(n) = n^4 and t(n) = O(N^4) The s

Find the big-O running time for each of these functions: T(n) = T(n - 2) + n ^2 Our Answers: n^2, n^3 T(n) = 3T(n/2) + n Our Answers: O(n log n), O(n^(log base 2 of 3)) T(n) = 2T(n/3) + n Our Ans

So I have been given a function, and I'll change the function since it is homework, and I want to learn HOW to do this instead of being told what the answer is. Using the definitions of big-Oh and Ω,

I asked a question about Big-Oh / Big-Theta but they acquired constants in them It is Big Oh and does not have any visible constants in it so I don't know where to start off with this since it is a s

I'm trying to compute the big-O time complexity of this selection sort implementation: void selectionsort(int a[], int n) { int i, j, minimum, index; for(i=0; i<(n-1); i++) { minimum=a[n-1]; index=

Decomposing a member function In a class there is a member function that is rather long. Let's say we have class Customer { public: void process(); ... }; The method process is by nature long and con

I have to find the big-O Notation of the following expression: 2n + n(logn)10 + (1/2)n If I ignore the coefficients, I get 2n + n (log n)10 plus some term involving 1/2. If I ignore the coefficients

A question in one of my past exams is a multi-choice question: Choose the FALSE statement: 7(log n) + 5n + n(log log n) + 3n(ln n) is A. O(n^2) B. Ω(n^2) C. O(n log^2 n) D. Ω(n) E. Θ(n log n) First I

Ok I am just learning about Big-O and someone gave me a conceptual question, to take as a means of trying to learn. However just barely starting out with Big-O I only know concept per say. I've been

Can some help me with a function which is Big O(1) but not Ω(1) and the other way around? Some explanation would greatly help.

I had a question about Big O vs little o notation. It seems intuitively, that Big O is like <= while little o is like <. Does that mean that if something is little o of f(n), it is also Big O of

Does anyone know how to make the following Matlab code approximate the exponential function more accurately when dealing with large and negative real numbers? For example when x = 1, the code works we

I have this recurrence: T(n) = T(n-1) + O(n log n) Then I guess the solution is T(n)=O(n log n) I use the substitution method. T(n)<= c*(n-1)*log (n-1) + O(n log n) T(n) <= c*n*log(n) + O(n log

I was reading about Big O notation. It stated, The big O of a loop is the number of iterations of the loop into number of statements within the loop. Here is a code snippet, for (int i=0 ;i<n; i+

im struggeling with something. If i estimate an exponential function with lm and using transformation ie. leastsquares.complete=lm(log(PPPrate)~Highest+Mortrate5Y+Crate+DummieJan+DummieDec,weights=No

I promise this is the last Big O question Big O Notation for following loops... for (int i = n; i > 0; i = i / 2){ for (int j = 0; j < n; j++){ count++; } } for (int k = 0; k < n; k++){ for

sum = 0; for (i=0;i<n/2;i++) for (j=i; j<n/4; j++) sum++; What is the big O for the above code? I calculated the big O but I'm not sure if it's correct. This is my answer the outer loop will r