Find the time complexity of the given code.
int count = 0;
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;
how is this o(N)
shouldnt it be logN as it get dec by factor of 2??
Time complexity
When will someone reply to this doubt??
Time complexity here is summation of N+N/2+N/4…1.
N(1+1/2+1/4…)
Now to get a lose approximation, consider the number of terms inside going to infinity.
Thus using formula for GP, term inside bracket sums to 1/(1-1/2) =2.
So 2*N is the answer for summation. Thus time complexity is O(N).
could u plz tell the time complexity of this code??just the time complexity only…IN TERMS OF N AND K…
plz reply …
usually in the case of dp the time complexity is the size of dp array itself.
but i dont think it is n2 here for this code …
here i think k will also play a role…
plz tell exact complexity…
Plz reply at the earliest plz
Plz reply else I will have to tell that even after 2 days doubt not solved by the ta…
Please provide with the logic and pseudo code for exact time complexity.
It is basically I am trying to count occurence of no in a given interval from previous to current index …
And if no occurs more than 1 times in that interval then I take two paths
first change the interval and start a new interval from that index …
2 to continue that interval only …and add 1 to its cost …
I have to minimise cost
Then i store ans for each interval …using 2 d dp…and use that to find min cost.
How much time will u take to reply.
you havent mentioned k in your logic.
K is the cost of starting a new interval …
Therefore if we start a new interval k gets added to cost …
Plz reply now…with a proper solution…and explaination once
Also since contest is over this is my solution for codechef 5 ques I am getting tle plz correct it …and also explain time complexity of my soln
Plz reply at the earliest…
It took u four days to reply to time complexity question…isn’t that strange…
Still you aren’t replying ???are u not able to solve this?? Plz tell clearly…there is no point in wasting time… reply
since you are not really altering the k througout the course of your code i’d say the complexity should be O(n^2) considering there is no bug in their code, which has high probability of existing since your code is anything but clean.
Then why did my code not get submit on codechef …why is it giving tle there plz and this as well…plz …
Since his less than 1000…
find the bug if any exists…plz give a clear ans …
if we assume 1000 test cases, then the number of loops would be greater than 10^8, since bug in the code is not related to the discussion topic i would suggest you to create new doubt